字符串的排列Java

刷题记录第22题，上一题：数据流中的中位数，本题地址：字符串的排列。

题目描述：

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

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

示例:

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

限制：

1 <= s 的长度 <= 8

这道题是一道典型的回溯法问题。在之前的八皇后问题的博客中也采用了回溯的思想。

在算法小抄的一书中说到：解决一个回溯问题，实际上就是一个决策树的遍历过程，且这个算法做的过程很基础，就是穷举过程。

• 路径：也就是已经做出的选择；
• 选择列表：也就是当前可做出的选择；
• 结束条件：也就是到达决策树底部，无法再做出选择的条件；

回溯算法的代码框架如下：

private void backtrack(路径， 选择列表){
    if 满足结束条件{
        result.add(路径)
        return
    }
    
    for 选择 in  选择列表{
        做选择
        backtrack(路径， 选择列表)
        撤销选择
    }
}
           

其核心也就在于，再

for

循环的递归，在递归调用前做出选择，在递归调用结束后撤销选择。

本题中输入的字符串，没有明确说明是否是每个字母只出现一次，所以这里的字母其实可以出现多次。也就是比如

aaa

这样的字符串。

解决该问题的一种较为直观的思路是，我们首先生成所有的排列，然后进行去重。而另一种思路是我们通过修改递归函数，使得该递归函数只会生成不重复的序列。

class Solution {
    private List<String> list;
    boolean[] vis;
    public String[] permutation(String s) {
        list = new ArrayList<>();
        vis = new boolean[s.length()];
        backtrack(s.toCharArray(), 0, s.length(), new StringBuffer());

        // 去重
        HashSet<String> strings = new HashSet<>(list); // List<String> list;
        String[] res = new String[strings.size()];
        int idx = 0;
        for (String string : strings) {
            res[idx++] = string;
        }
        return res;
    }
	
	// i 表示当前位置，n表示字符串长度
    private void backtrack(char[] arr, int i, int length, StringBuffer stringBuffer) {
        if(i == length && stringBuffer.length() > 0){
            list.add(stringBuffer.toString());
            return;
        }
        for (int j = 0; j < length; j++) {
            if(vis[j])
                continue;
            vis[j] = true;
            stringBuffer.append(arr[j]);
            backtrack(arr, i + 1, length, stringBuffer);// 探测下一个位置
            stringBuffer.deleteCharAt(stringBuffer.length() - 1);
            vis[j] = false;
        }
    }
}
           

另一种，在递归函数中去重的思路为：在递归函数中设定一个规则，保证在填每一个空位的时候重复字符只会被填入一次。具体地，我们首先对原字符串排序，保证相同的字符都相邻，在递归函数中，我们限制每次填入的字符一定是这个字符所在重复字符集合中「从左往右第一个未被填入的字符」，即如下的判断条件：

if (vis[j] || (j > 0 && !vis[j - 1] && s[j - 1] == s[j])) {
    continue;
}