无重复字符串的排列组合

无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。

示例1:

 输入：S = "qwe"
 输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]
示例2:

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

字符都是英文字母。
字符串长度在[1, 9]之间。
通过次数13,360提交次数16,468

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutation-i-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

1. 首先求所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换,求后面所有字符的排列。

2. 仍把后面的所有字符分成两部分：后面字符的第一个字符，以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换

class Solution {
    public String[] permutation(String S) {
        if (S == null || S.length() == 0) return new String[]{};
        char[] arr = S.toCharArray();
        int len = 1;
        for (int i = 2; i <= S.length(); i++) {                                     //计算结果数组大小
            len = len * i;
        }
        String[] res = new String[len];
        backtrack(arr, 0, arr.length, res);                                   //回溯求解
        return res;
    }
    int index = 0;

    public void backtrack(char[] arr, int start, int n, String[] res) {

        if (start == n - 1) {
            StringBuilder bd = new StringBuilder();
            for (int i = 0; i < arr.length; i++) {
                bd.append(arr[i]);
            }
            res[index] = bd.toString();
            index++;
            return;
        }

        for (int i = start; i < arr.length; i++) {
            swap(arr, start, i);                                                    //交换
            backtrack(arr, start + 1, n, res);
            swap(arr, start, 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) {
        List<String> list = new ArrayList<>();
        list.add(S);
        for (int i = 0; i < S.length() - 1; i++) {
            int size = list.size();
            for (int j = i + 1; j < S.length(); j++) {
                for (int index = 0; index < size; index++) {
                    list.add(swap(list.get(index), i, j));
                }
            }
        }
        return list.toArray(new String[list.size()]);
    }
    //交换位置
    private String swap(String s, int pos1, int pos2) {
        char[] chars = s.toCharArray();
        chars[pos1] ^= chars[pos2];
        chars[pos2] ^= chars[pos1];
        chars[pos1] ^= chars[pos2];
        return new String(chars);
    }
}

参考文献

作者：LineCutFeng
链接：https://leetcode-cn.com/problems/permutation-i-lcci/solution/shu-wo-zhi-yan-zai-zuo-de-ge-wei-du-shi-hao-yang-d/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信