【LeetCode】剑指 Offer 38. 字符串的排列

• 【LeetCode】剑指 Offer 38. 字符串的排列

package offer;

import java.util.HashSet;
import java.util.linkedList;
import java.util.List;

public class Solution38 {
    public static void main(String[] args) {
        String s = "abc";
        Solution38 solution = new Solution38();
        String[] res = solution.method(s);
        System.out.print("[");
        for(int i = 0; i < res.length; i++){
            System.out.print('"');
            System.out.print(res[i]);
            System.out.print('"');
            if(i != res.length - 1) System.out.print(",");
        }
        System.out.print("]");
    }

    char[] c;
    List res = new linkedList<>();

    private String[] method(String s){
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }

    private void dfs(int x){
        if(x == c.length - 1){
            res.add(String.valueOf(c));
            return;
        }
        HashSet set = new HashSet<>();
        for(int i = x; i < c.length; i++){
            if(set.contains(c[i])) continue;	//重复则不交换
            set.add(c[i]);
            swap(i, x);
            dfs(x+1);
            swap(i, x);
        }
    }

    private  void swap(int a, int b){
        char temp = c[a];
        c[a] = c[b];
        c[b] = temp;
    }
}

//时间复杂度为 O(n*n!)
//空间复杂度为 O(n^2)，递归中辅助 Set 累计存储的字符数量最多为 N + (N-1) + ... + 2 + 1 = (N+1)N/2N+(N−1)+...+2+1=(N+1)N/2