题解 | #字符串的排列#

ChatGPT 给的解释，佬们参考：

我们来逐步梳理关于字符串 abb 的递归排列过程，结合回溯和去重的具体细节。通过对排列树的逐层展开，我们会展示每一步的选择和判断。

代码讲解

以下是完整代码：

import java.util.*;

public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> result = new ArrayList<>();
        if (str == null || str.trim().isEmpty()) {
            return result;
        }

        // 转字符数组并排序
        char[] charStr = str.toCharArray();
        Arrays.sort(charStr); // 排序以便处理重复字符

        boolean[] vis = new boolean[str.length()]; // 标记数组，记录每个字符是否被使用
        StringBuilder temp = new StringBuilder();  // 临时构建字符串

        // 递归构建排列
        backtrack(result, charStr, temp, vis);
        return result;
    }

    private void backtrack(ArrayList<String> res, char[] str, StringBuilder temp, boolean[] vis) {
        // 递归终止条件：当临时字符串的长度等于输入字符串长度
        if (temp.length() == str.length) {
            res.add(temp.toString());
            return;
        }

        for (int i = 0; i < str.length; i++) {
            // 跳过已经使用的字符
            if (vis[i]) {
                continue;
            }

            // 跳过重复字符：只有当前字符是重复字符且其前一个重复字符已被使用过才进入下一个递归
            if (i > 0 && str[i] == str[i - 1] && !vis[i - 1]) {
                continue;
            }

            // 选择当前字符，并标记为已使用
            vis[i] = true;
            temp.append(str[i]);

            // 递归进入下一层
            backtrack(res, str, temp, vis);

            // 回溯，撤销选择
            vis[i] = false;
            temp.deleteCharAt(temp.length() - 1);
        }
    }
}

递归过程详解

使用示例 str = "abb" 来逐步分析递归和回溯的展开过程，重点关注字符的使用与回溯状态。

初始条件

• 输入字符串 abb 被转换为字符数组 ['a', 'b', 'b']，并已排序。
• 创建一个 vis 数组，初始值为 [false, false, false]，表示字符未被使用。

递归展开（每一步详解）

1. 第一级递归：temp = ""循环遍历字符数组 str： i = 0，字符 'a'： 未被使用 (vis[0] = false)。添加 'a' 到 temp，temp = "a"，标记 vis[0] = true。进入下一层递归。
2. 第二级递归：temp = "a"循环遍历字符数组 str： i = 0，字符 'a'：已使用，跳过。i = 1，字符 'b'： 未被使用 (vis[1] = false)。添加 'b' 到 temp，temp = "ab"，标记 vis[1] = true。进入下一层递归。
3. 第三级递归：temp = "ab"循环遍历字符数组 str： i = 0，字符 'a'：已使用，跳过。i = 1，字符 'b'：已使用，跳过。i = 2，字符 'b'： 未被使用 (vis[2] = false)。添加 'b' 到 temp，temp = "abb"，标记 vis[2] = true。此时，temp 的长度等于 str 的长度，保存排列 "abb"，并回溯到上一级。
4. 回溯到第三级：temp = "ab"撤销最后一步选择，将 temp 恢复为 "ab"，vis[2] = false。第三级循环结束，返回到第二级。
5. 回溯到第二级：temp = "a"撤销上一步选择，将 temp 恢复为 "a"，vis[1] = false。继续第二级的循环。 i = 2，字符 'b'： str[2] == str[1] 且 !vis[1]，跳过以避免重复排列。第二级循环结束，返回到第一级。
6. 回溯到第一级：temp = ""撤销选择，将 temp 恢复为空，vis[0] = false。继续第一级循环。 i = 1，字符 'b'： 添加 'b' 到 temp，temp = "b"，标记 vis[1] = true。进入下一层递归。
7. 后续递归过程类似上述步骤，在第一级和第二级递归中依次选择 'a' 和 'b'，获得排列 "bab" 和 "bba"，然后完成回溯，最终返回结果。

最终结果

• 通过这种逐层递归、选择与回溯，结果包含所有不同的排列：

总结

该递归和回溯过程主要依赖标记数组 vis 来控制字符的选择状态，并在同一级递归中通过去重条件 (str[i] == str[i - 1] && !vis[i - 1]) 来跳过重复字符。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串ArrayList
     */
    public ArrayList<String> Permutation (String str) {
        // write code here
        ArrayList<String> result = new ArrayList<String>();
        if (str == null || str.trim().length() == 0) {
            return result;
        }
        // 转字符数组
        char[] charStr = str.toCharArray();
        // 按字典排序
        Arrays.sort(charStr);
        // 创建临时数组，标记字符的使用状态
        boolean[] vis = new boolean[str.length()];
        Arrays.fill(vis, false);
        // 临时变量缓存某个排序字符串
        StringBuffer temp = new StringBuffer();
        // 递归构建
        recursion(result, charStr, temp, vis);
        return result;
    }

    private void recursion(ArrayList<String> res, char[]str, StringBuffer temp,
                           boolean[]vis) {
        // 临界值
        if (temp.length() == str.length) {
            res.add(new String(temp));
            return;
        }
        // 遍历所有字符元素选取一个加入
        for (int i = 0; i < str.length; i++) {
            //
            if (vis[i]) {
                continue;
            }
            // 元素重复，且前一个元素已经使用 abb
            if (i > 0 && str[i - 1] == str[i] && !vis[i - 1]) {
                continue;
            }
            // 标记使用过
            vis[i] = true;
            // 拼入临时字符串
            temp.append(str[i]);
            recursion(res, str, temp,
                      vis); // 递归返回只在当前函数作用域内有效，返回后不会拦截后序执行
            // 回溯
            vis[i] = false;
            temp.deleteCharAt(temp.length() - 1);
        }
    }
}