题解 | #NC121 字符串的排列#

和力扣 剑指 Offer 38. 字符串的排列 相同

import java.util.*;
public class Solution {
    ArrayList<String> res = new ArrayList<>();
    public ArrayList<String> Permutation(String s) {
        char[] c = s.toCharArray();
        back(c, 0);
        return res;
    }
    
    public void back(char[] c, int idx) {
        if (idx == c.length - 1) {
            res.add(String.valueOf(c));     //字符数组转字符串
            return;
        }
        HashSet<Character> set = new HashSet<>();    //每个递归栈帧中都有一个独立的 set
        for (int i = idx; i < c.length; i++) {
            if (set.contains(c[i])) continue;
            set.add(c[i]);
            swap(c, idx, i);
            back(c, idx + 1);   //注意这里得是 idx + 1 而不是 i + 1
            swap(c, idx, i);
        }
    }

    public void swap(char[] c, int idx1, int idx2) {
        if (idx1 == idx2) return;
        char tmp = c[idx1];
        c[idx1] = c[idx2];
        c[idx2] = tmp;
    }
}