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

有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。

示例1:

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

示例2:

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

提示:

• 字符都是英文字母。
• 字符串长度在[1, 9]之间。

1.集合去重
Python:

class Solution:
    def permutation(self, S: str) -> List[str]:
        arr = list(S)
        arr.sort()
        lis = []
        flag = [1 for i in range(len(arr))]
        def backtrace(arr, res):
            if len(res) == len(arr):
                lis.append(''.join(res))
                return
            for i in range(len(arr)):
                if flag[i]:
                    if i-1 >= 0 and arr[i] == arr[i-1] and flag[i-1]:
                        continue
                    res.append(arr[i])
                    flag[i] = 0
                    backtrace(arr, res)
                    res.pop()
                    flag[i] = 1
        backtrace(arr, [])
        return lis

2.排序跳过重复
Python:

class Solution:
    def permutation(self, S: str) -> List[str]:
        arr = list(S)
        arr.sort()
        lis = []
        flag = [1 for i in range(len(arr))]
        def backtrace(arr, res):
            if len(res) == len(arr):
                lis.append(''.join(res))
                return
            for i in range(len(arr)):
                if flag[i]:
                    if i-1 >= 0 and arr[i] == arr[i-1] and flag[i-1]:
                        continue
                    res.append(arr[i])
                    flag[i] = 0
                    backtrace(arr, res)
                    res.pop()
                    flag[i] = 1
        backtrace(arr, [])
        return lis

Java:

class Solution {
    public String[] permutation(String S) {
        List<String> result = new ArrayList<String>();
        boolean[] flag = new boolean[S.length()];
        char[] s = S.toCharArray();
        Arrays.sort(s);
        backtrace(result, flag, String.valueOf(s), "");
        return result.toArray(new String[result.size()]);
    }

    public void backtrace(List<String> r, boolean[] flag, String s, String t)
    {
        if(t.length() == s.length())
        {
            r.add(t);
        }
        for(int i = 0; i < s.length(); i++)
        {
            if(!flag[i])
            {
                if(i > 0 && !flag[i-1] && s.charAt(i) == s.charAt(i-1))
                {
                    continue;
                }
                flag[i] = true;
                backtrace(r, flag, s, t+s.charAt(i));
                flag[i] = false;
            }
        }
    }
}