面试题 08.06. 汉诺塔问题

题目

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

示例1:
输入：S = “qwe”
输出：[“qwe”, “qew”, “wqe”, “weq”, “ewq”, “eqw”]

示例2:
输入：S = “ab”
输出：[“ab”, “ba”]

提示:

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

题解

public String[] permutation(String S) {
    char[] chars = S.toCharArray();
    List<String> result = new ArrayList<>();
    if (chars.length == 0) {
        return new String[0];
    }

    Consumer<Integer> recursion = new Consumer<Integer>() {
        @Override
        public void accept(Integer index) {
            if (index == chars.length) {
                result.add(new String(chars));
                return;
            }

            for (int i = index; i < chars.length; i++) {
                // 选定的字符移动到索引位置 并交换两个位置的字符
                char temp = chars[index];
                chars[index] = chars[i];
                chars[i] = temp;
                this.accept(index + 1);
                // 回溯
                chars[i] = chars[index];
                chars[index] = temp;
            }
        }
    };
    recursion.accept(0);

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