题解 | 字符串的排列

import java.util.*; 

import java.lang.*;
import java.util.stream.Collectors;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串ArrayList
     */
    public ArrayList<String> Permutation (String str) {
        char[] num=str.toCharArray();
        Arrays.sort(num); // 关键：排序使相同数字相邻
        boolean[] used = new boolean[num.length];
        ArrayList<String> result = new ArrayList<>();
        LinkedList<Character> trace = new LinkedList<>();
        backtrack(result, used, trace, num);
        return result;
    }

    private void backtrack(ArrayList<String> result, boolean[] used, 
                           LinkedList<Character> trace, char[] num) {
        if (trace.size() == num.length) {
           String ss= trace.stream().map(String::valueOf).collect(Collectors.joining());
            result.add( ss);
            return;
        }
        
        for (int i = 0; i < num.length; i++) {
            // 剪枝条件：当前数字与前一个相同，且前一个未被使用 => 跳过
            if (used[i] || (i > 0 && num[i] == num[i - 1] && !used[i - 1])) {
                continue;
            }
            
            used[i] = true;
            trace.add(num[i]);
            backtrack(result, used, trace, num);
            trace.removeLast();
            used[i] = false;
        }
    }
}