剑指 Offer 38. 字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

限制：

• 1 <= s 的长度 <= 8

Python:

class Solution:
    def permutation(self, s: str) -> List[str]:
        res = []
        flag = [0 for i in range(len(s))]
        def helper(s, ini, flag):
            nonlocal res
            if len(ini) == len(s):
                res.append(ini)
                return
            for i in range(len(s)):
                if not flag[i]:
                    flag[i] = 1
                    helper(s, ini+s[i], flag)
                    flag[i] = 0
        helper(s, "", flag)
        return list(set(res))

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;
            }
        }
    }
}