面试题 08.08. 有重复字符串的排列组合

刷题 leetcode

题目：有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。
示例1:

输入：S = "qqe"
输出：["eqq","qeq","qqe"]

示例2:

输入：S = "ab"
输出：["ab", "ba"]

提示:
1. 字符都是英文字母。
2. 字符串长度在[1, 9]之间。

链接：https://leetcode-cn.com/problems/permutation-ii-lcci

与面试题 08.07. 无重复字符串的排列组合思路类似，只是多了一步去重

public class Main {
    List<String> list = new ArrayList<>();  //存放单词的所有排列组合结果集
    public String[] permutation(String S) {
        char[] chars = S.toCharArray();
        //如果要求字典序，对chars数组提前排序Arrays.sort(chars) || 最后对list结果集排序 list.sort(null)
        backtrack(chars, 0);
        return list.toArray(new String[0]);
    }
    //c:单词的字符数组    k:要交换的元素下标
    private void backtrack(char[] c, int k) {
        if(k == c.length-1){
            list.add(new String(c));
            return;
        }
        Set<Character> set = new HashSet<>();
        for(int i=k; i<c.length; i++){
            //通过字符数组中相同的字母只取第一个来去重
            if(!set.contains(c[i])) {
                set.add(c[i]);
                swap(c, i, k);  //交换
                backtrack(c, k+1);  //回溯
                swap(c, i, k);  //还原
            }
        }
    }
    private void swap(char[] c, int i, int j) {
        char temp = c[i];
        c[i] = c[j];
        c[j] = temp;
    }
}