字符串的排列

2020-12-19

剑指 Offer 38. 字符串的排列

难度中等357

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

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

示例:

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

限制：

1	1 <= s 的长度 <= 8

回溯

class Solution {
    public String[] permutation(String s) {
        char [] arr= s.toCharArray();
        backtrack(arr,0);
        return res.toArray(new String[res.size()]);
    }

    List<String> res = new ArrayList<>();
    public void backtrack(char []arr,int idx){
        if(idx == arr.length-1){
            res.add(String.valueOf(arr));
            return;
        }
        Set<Character> set = new HashSet<>();
        for(int i = idx;i < arr.length;i++){
            if(set.contains(arr[i]))continue;
            set.add(arr[i]);
            swap(arr,idx,i);
            backtrack(arr,idx+1);
            swap(arr,idx,i);
        }
    }
    public void swap(char []arr,int index1,int index2){
        char temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

回溯去重

class Solution {
    public String[] permutation(String s) {
        Set<String> resultSet = new HashSet<>();
        List<Character> charList = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            charList.add(s.charAt(i));
        }

        backtrack(charList, s.length(), new StringBuilder(), resultSet);
        String[] res = new String[resultSet.size()];

        int count=0;
        for(String str:resultSet){
            res[count]=str;
            count++;
        }

        return res;
    }
    public void backtrack(List<Character> list, int n, StringBuilder bd, Set<String> resultSet) {
        if (bd.length() == n) {
            resultSet.add(bd.toString());
        } else {
            for (int i = 0; i < list.size(); i++) {
                char c = list.get(i);
                bd.append(c);
                list.remove(i);
                backtrack(list, n, bd, resultSet);
                bd.deleteCharAt(bd.length() - 1);
                list.add(i, c);
            }
        }
    }
}

高效的写法

我们求整个字符串的排列，可以看成两步：

首先求所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换。
固定第一个字符，求后面所有字符的排列。这个时候我们仍把后面的所有字符分成两部分：后面字符的第一个字符，以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换

（套娃）

class Solution {
    List<String> res = new LinkedList<>();
    char[] c;
    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }
    void dfs(int x) {
        if(x == c.length - 1) {
            res.add(String.valueOf(c)); // 添加排列方案
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for(int i = x; i < c.length; i++) {
            if(set.contains(c[i])) continue; // 重复，因此剪枝
            set.add(c[i]);
            swap(i, x); // 交换，将 c[i] 固定在第 x 位 
            dfs(x + 1); // 开启固定第 x + 1 位字符
            swap(i, x); // 恢复交换
        }
    }
    void swap(int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }
}

如果输入n个字符，则这n个字符能构成长度为1的组合、长度为2的组合、……、长度为n的组合。

在求n个字符的长度为m（1≤m≤n）的组合的时候，我们把这 n 个字符分成两部分：

第一个字符和其余的所有字符。

如果组合里包含第一个字符，则下一步在剩余的字符里选取m-1个字符；
如果组合里不包含第一个字符，则下一步在剩余的 n-1 个字符里选取m个字符。

也就是说，我们可以把求n个字符组成长度为m的组合的问题分解成两个子问题，分别求n-1个字符串中长度为m-1的组合，以及求n-1个字符的长度为m的组合。这两个子问题都可以用递归的方式解决。

参考文献

面试题38. 字符串的排列（回溯法，清晰图解）