如何使用 StringBuilder 实现字符串全排列（Java 教程）

本文详解如何用 stringbuilder 高效实现字符串全排列，避免字符串拼接开销，并修正递归回溯中常见的状态重置错误，确保输出完整、无重复、无越界异常。

在 Java 中，使用 String 实现全排列虽直观，但因 String 不可变，每次拼接都会创建新对象，时间与空间开销较大。而 StringBuilder 是可变的、线程不安全但高性能的字符序列容器，更适合递归回溯类操作——前提是必须精准管理其状态：进入递归前修改，返回后彻底还原。

下面是一个正确、健壮、可直接运行的 StringBuilder 版全排列实现：

public class PermutationWithStringBuilder {
    public static void permutations(StringBuilder str, StringBuilder ans) {
        // 递归终止条件：原字符串已选尽
        if (str.length() == 0) {
            System.out.println(ans);
            return;
        }

        // 遍历当前可选的所有字符位置
        for (int i = 0; i < str.length(); i++) {
            char currentChar = str.charAt(i);

            // ✅ 步骤1：将当前字符加入答案路径
            ans.append(currentChar);

            // ✅ 步骤2：从原字符串中移除该字符（构建剩余待选序列）
            str.deleteCharAt(i);

            // ✅ 步骤3：递归处理剩余字符
            permutations(str, ans);

            // ⚠️ 关键：回溯还原！必须严格逆序执行
            // 步骤4：从答案中移除最后添加的字符（注意：不是 deleteCharAt(i)，而是末尾！）
            ans.deleteCharAt(ans.length() - 1);

            // 步骤5：将当前字符插回原位置，恢复 str 状态
            str.insert(i, currentChar);
        }
    }

    public static void main(String[] args) {
        StringBuilder input = new StringBuilder("abc");
        StringBuilder answer = new StringBuilder();
        permutations(input, answer);
    }
}

输出结果：

abc
acb
bac
bca
cab
cba

✅ 核心要点解析：

• ans.append(...) 和 ans.deleteCharAt(ans.length() - 1) 构成一对原子操作：添加 → 递归 → 撤销，确保每层递归的 ans 独立且干净；
• str.deleteCharAt(i) 后，str 长度减 1，后续索引整体前移；因此回溯时必须用 str.insert(i, ch) 将字符插回原下标 i（而非 replace 或 append），否则位置错乱导致 StringInde

  

  xOutOfBoundsException；
• ❌ 原代码中 ans.deleteCharAt(i) 是典型错误：i 是原字符串的索引，而 ans 当前长度可能远大于 i，且其末尾字符位置恒为 ans.length()-1；
• ❌ newstr.replace(i, i, ...) 逻辑错误：replace(start, end, ...) 的 end 是排他性索引，replace(i,i,...) 相当于在位置 i 插入，但此时 i 已越界（因 deleteCharAt(i) 后 newstr.length() 减小）。

? 进阶建议：

• 若需收集所有排列而非仅打印，可将 System.out.println(ans) 替换为 resultList.add(ans.toString())；
• 对含重复字符的字符串（如 "aab"），可在循环内增加去重判断：if (i == 0 || str.charAt(i) != str.charAt(i-1))（需先排序）；
• 时间复杂度仍为 O(n×n!)，但 StringBuilder 显著降低常数因子，尤其对长字符串更友好。

掌握 StringBuilder 在回溯中的“修改–递归–还原”三步法，是写出高效、无 Bug 递归算法的关键能力。