面试题 08.07. 无重复字符串的排列组合

刷题 leetcode

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

示例1:

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

示例2:

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

提示:
1. 字符都是英文字母。
2. 字符串长度在[1, 9]之间。

链接：https://leetcode-cn.com/problems/permutation-i-lcci

class Solution {
    List<String> list = new ArrayList<>();//存放所有可能排序的集合
    public String[] permutation(String S) {
        char[] chars = S.toCharArray();
        //如果要求字典序，对chars数组提前排序Arrays.sort(chars)或者最后对list排序 list.sort(null)
        backtrack(S.toCharArray(), 0);
        return list.toArray(new String[list.size()]);
    }
    //c:要排序的字符数组  k:要交换元素的下标
    private void backtrack(char[] c, int k){
        if(k == c.length-1){//递归到最后一个元素
            list.add(new String(c));
            return;
        }
        for(int i=k; i<c.length; i++){
            swap(c, i, k);//交换
            backtrack(list, c, k+1);//回溯
            swap(c, i, k);//还原
        }
    }
    private void swap(char[] c, int i, int j){
        char temp = c[i];
        c[i] = c[j];
        c[j] = temp;
    }
}