剑指 Offer 38. 字符串的排列

• 题目链接：剑指 Offer 38. 字符串的排列 (opens new window)；
• 题解链接：回溯算法（Java） (opens new window)。

题目描述

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

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

示例:

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

限制：

1 <= s 的长度 <= 8

思路分析

这道题其实就是字符上的全排列问题，使用回溯算法就可以完成。

参考题解：

• 「力扣」第 46 题题解：从全排列问题开始理解「回溯搜索」算法（深度优先遍历 + 状态重置 + 剪枝） (opens new window)；

介绍了全排列问题的复杂度计算，但是本题有剪枝（和输入数据相关），所以讨论复杂度计算是复杂的，可以忽略。

• 「力扣」第 47 题题解：回溯搜索 + 剪枝 (opens new window)。

参考代码：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {

    public String[] permutation(String s) {
        int len = s.length();
        if (len == 0) {
            return new String[0];
        }

        // 转换成字符数组是常见的做法
        char[] charArr = s.toCharArray();
        // 排序是为了去重方便
        Arrays.sort(charArr);

        // 由于操作的都是字符，使用 StringBuilder
        StringBuilder path = new StringBuilder();
        boolean[] used = new boolean[len];

        // 为了方便收集结果，使用动态数组
        List<String> res = new ArrayList<>();
        dfs(charArr, len, 0, used, path, res);

        // 记得转成字符串数组
        return res.toArray(new String[0]);
    }

    /**
     * @param charArr 字符数组
     * @param len     字符数组的长度
     * @param depth   当前递归深度
     * @param used    当前字符是否使用
     * @param path    从根结点到叶子结点的路径
     * @param res     保存结果集的变量
     */
    private void dfs(char[] charArr,
                     int len,
                     int depth,
                     boolean[] used,
                     StringBuilder path,
                     List<String> res) {
        if (depth == len) {
            // path.toString() 恰好生成了新的字符对象
            res.add(path.toString());
            return;
        }
        for (int i = 0; i < len; i++) {
            if (!used[i]) {
                if (i > 0 && charArr[i] == charArr[i - 1] && !used[i - 1]) {
                    continue;
                }
                used[i] = true;
                path.append(charArr[i]);

                dfs(charArr, len, depth + 1, used, path, res);

                // 递归完成以后，需要撤销选择，递归方法执行之前做了什么，递归方法执行以后就需要做相应的逆向操作
                path.deleteCharAt(path.length() - 1);
                used[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] res = solution.permutation("aba");
        System.out.println(Arrays.toString(res));
    }
}

---

作者：liweiwei1419 链接：https://suanfa8.com/backtracking/solutions-1/38-zi-fu-chuan-de-pai-lie-lcof 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。