剑指 Offer 38. 字符串的排列

题目

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

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

示例:
输入：s = “abc”
输出：[“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]

限制：
1 <= s 的长度 <= 8

题解

public String[] permutation(String s) {
    int len = s.length();
    char[] chars = s.toCharArray();
    Set<String> result = new HashSet<>();
    Consumer<Integer> backtrack = new Consumer<Integer>() {
        @Override
        public void accept(Integer index) {
            if (index == len) {
                result.add(new String(chars));
                return;
            }
            // index位置已经使用过的字符 去重
            Set<Character> used = new HashSet<>();
            for (int i = index; i < len; i++) {
                if (!used.contains(chars[i])) {
                    used.add(chars[i]);
                    // 交换字符位置 保证index之后的字符都是未使用过的
                    char temp = chars[index];
                    chars[index] = chars[i];
                    chars[i] = temp;

                    this.accept(index + 1);
                    // 回溯
                    chars[i] = chars[index];
                    chars[index] = temp;
                }
            }
        }
    };
    backtrack.accept(0);

    return result.toArray(new String[0]);
}