字符串型回溯：分割、括号生成与 IP 地址恢复

摘要

字符串型回溯题有一个共同特征：不再从数字数组中”选元素”，而是在字符串上”选切割点”或”选下一个字符”，通过分析字符串的结构约束来剪枝。本文覆盖三道经典题：Palindrome Partitioning（回文分割）、Generate Parentheses（括号生成）、Restore IP Addresses（恢复 IP 地址）。这三道题共同展示了字符串回溯的核心技法——前向约束检查：在做选择之前就验证合法性，而不是生成完整字符串再筛选。

第 1 章字符串回溯的通用模型

1.1 从”选元素”到”选切割点”

组合/排列型回溯的搜索树，每层从候选集合中选一个元素加入路径。

字符串型回溯的搜索树，每层选一个分割点，将字符串切割为前缀（加入路径）和后缀（继续处理）：

字符串 "abc" 的分割搜索树：

                ""（待处理）
         /          |         \
       ["a"]      ["ab"]    ["abc"]
  ("bc"待处理) ("c"待处理)   (空，结束)
    /     \         \
["a","b"] ["a","bc"] ["ab","c"]
  \           (不合法，...剪枝)
["a","b","c"]

搜索树的层数等于字符串的分割次数，深度取决于字符串长度。

1.2 字符串回溯的通用框架

void backtrack(String s, int start, List<String> path, List<List<String>> result) {
    // 结束条件：已处理完整字符串
    if (start == s.length()) {
        result.add(new ArrayList<>(path));
        return;
    }
    // 枚举分割点：从 start 到 s.length()-1
    for (int end = start + 1; end <= s.length(); end++) {
        String segment = s.substring(start, end);
 
        // 合法性检查（前向约束）
        if (!isValid(segment)) continue;  // 不合法，跳过这个切割
 
        path.add(segment);
        backtrack(s, end, path, result);  // end 成为下一层的 start
        path.remove(path.size() - 1);    // 回溯
    }
}

关键：isValid 函数在”做选择之前”检查，而不是递归完再检查。这是字符串回溯的核心优化——合法性检查即剪枝。

第 2 章 LeetCode 131：Palindrome Partitioning

2.1 题目

LeetCode 131 - Palindrome Partitioning（中等）：

给你一个字符串 s，请将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

输入：s = "a"
输出：[["a"]]

2.2 核心实现

public List<List<String>> partition(String s) {
    List<List<String>> result = new ArrayList<>();
    backtrack(s, 0, new LinkedList<>(), result);
    return result;
}
 
private void backtrack(String s, int start, LinkedList<String> path, List<List<String>> result) {
    if (start == s.length()) {
        result.add(new ArrayList<>(path));
        return;
    }
    for (int end = start + 1; end <= s.length(); end++) {
        // 前向检查：只有回文子串才进入递归
        if (isPalindrome(s, start, end - 1)) {
            path.addLast(s.substring(start, end));
            backtrack(s, end, path, result);
            path.removeLast();
        }
    }
}
 
private boolean isPalindrome(String s, int left, int right) {
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) return false;
        left++;
        right--;
    }
    return true;
}

时间复杂度： $O (n \cdot 2^{n})$ 。分割方案最多 $2^{n - 1}$ 种（每个位置是否切割），每种方案检查回文需要 $O (n)$ ，总计 $O (n \cdot 2^{n})$ 。

2.3 优化：预处理回文 DP

如果字符串很长，每次调用 isPalindrome 的代价是 $O (n)$ ，可以用动态规划预处理所有子串的回文性：

// dp[i][j] = true 表示 s[i..j] 是回文串
boolean[][] dp = new boolean[n][n];
 
// 所有长度为 1 的子串都是回文
for (int i = 0; i < n; i++) dp[i][i] = true;
 
// 长度为 2 的子串
for (int i = 0; i < n - 1; i++) dp[i][i+1] = (s.charAt(i) == s.charAt(i+1));
 
// 长度 >= 3 的子串
for (int len = 3; len <= n; len++) {
    for (int i = 0; i + len - 1 < n; i++) {
        int j = i + len - 1;
        dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i+1][j-1];
    }
}

预处理代价 $O (n^{2})$ ，之后每次回文判断 $O (1)$ ，将整体复杂度降为 $O (2^{n})$ （当字符串非常长、回文分割方案很多时，这个优化是值得的）。

2.4 搜索树模拟

s = "aab"：

backtrack(start=0, path=[])
  end=1: "a" 是回文 → path=["a"]
    backtrack(start=1, path=["a"])
      end=2: "a" 是回文 → path=["a","a"]
        backtrack(start=2, path=["a","a"])
          end=3: "b" 是回文 → path=["a","a","b"]
            start==3，收集！→ ["a","a","b"]
      end=3: "ab" 不是回文，跳过
  end=2: "aa" 是回文 → path=["aa"]
    backtrack(start=2, path=["aa"])
      end=3: "b" 是回文 → path=["aa","b"]
        start==3，收集！→ ["aa","b"]
  end=3: "aab" 不是回文，跳过

结果：[["a","a","b"],["aa","b"]] ✅

第 3 章 LeetCode 22：Generate Parentheses

3.1 题目

LeetCode 22 - Generate Parentheses（中等）：

数字 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且有效的括号组合。

输入：n=3
输出：["((()))","(()())","(())()","()(())","()()()"]

3.2 括号合法性的状态约束

合法括号序列需满足两个条件：

左括号数量 = 右括号数量 = n（总长 2n）
在序列的任意前缀中，左括号数量 >= 右括号数量（不能提前关括号）

这两个条件给出了何时可以加左括号、何时可以加右括号：

加左括号：当前左括号数 open < n（还有剩余配额）
加右括号：当前右括号数 close < open（已有未匹配的左括号）

每次做的”选择”不是从候选集合中选，而是选择下一个字符是 ( 还是 )。

3.3 实现

public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    backtrack(n, 0, 0, new StringBuilder(), result);
    return result;
}
 
private void backtrack(int n, int open, int close,
                        StringBuilder path, List<String> result) {
    // 结束条件：生成了 2n 个字符
    if (path.length() == 2 * n) {
        result.add(path.toString());
        return;
    }
 
    // 选择 1：加左括号（前提：open < n）
    if (open < n) {
        path.append('(');
        backtrack(n, open + 1, close, path, result);
        path.deleteCharAt(path.length() - 1);  // 回溯
    }
 
    // 选择 2：加右括号（前提：close < open）
    if (close < open) {
        path.append(')');
        backtrack(n, open, close + 1, path, result);
        path.deleteCharAt(path.length() - 1);  // 回溯
    }
}

为什么这里没有 for 循环？

括号生成每步只有两个选择（( 或 )），且两个选择都有明确的合法条件。不满足条件的选择直接不进入——这实际上就是两个独立的分支，比 for 循环 + continue 更清晰。

3.4 搜索树（n=2）

backtrack(open=0, close=0)
  加 ( → open=1
    加 ( → open=2
      加 ) → close=1（close<open=2）
        加 ) → close=2（close<open=2）
          结束："(())" ✅
    加 ) → close=1（close<open=1）
      加 ( → open=2
        加 ) → close=2
          结束："()()" ✅

搜索树的大小：括号序列的数量等于第 n 个卡特兰数（Catalan Number） $C_{n} = \frac{1}{n + 1} (n 2 n)$ ，约为 $\frac{4 ^{n}}{n ^{3/2} π}$ 。对于 n=3， $C_{3} = 5$ ，恰好与输出数量吻合。

3.5 有效约束 vs 暴力生成再过滤

暴力方法：生成所有 $2^{2 n}$ 个由 ( 和 ) 组成的字符串，再过滤出合法的。当 n=8， $2^{16} = 65536$ ，但合法括号序列只有 $C_{8} = 1430$ 个——绝大多数时间浪费在无效路径上。

回溯方法：通过 open < n 和 close < open 的约束，只生成合法的路径。搜索树中的每一条从根到叶的路径，都对应一个合法的括号序列，没有任何无效路径的浪费。这是约束传播（Constraint Propagation）思想的典型应用。

第 4 章 LeetCode 93：Restore IP Addresses

4.1 题目

LeetCode 93 - Restore IP Addresses（中等）：

给你一个只含数字的字符串 s，用以表示一个 IP 地址，返回所有可能从 s 获得的有效 IP 地址。有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导零），整数之间用 . 分隔。

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

输入：s = "0000"
输出：["0.0.0.0"]

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

4.2 IP 地址的结构约束

IP 地址有严格结构：恰好 4 段，每段是 0-255 的整数，且不能有前导零（01 不合法，0 合法）。

这些约束全部可以在”选择切割点”时做前向检查：

boolean isValidSegment(String s, int start, int end) {
    int len = end - start + 1;
    if (len > 3) return false;           // 超过 3 位
    if (len > 1 && s.charAt(start) == '0') return false;  // 前导零
    int val = Integer.parseInt(s.substring(start, end + 1));
    return val >= 0 && val <= 255;       // 数值范围
}

4.3 实现

public List<String> restoreIpAddresses(String s) {
    List<String> result = new ArrayList<>();
    if (s.length() < 4 || s.length() > 12) return result;  // 快速排除
    backtrack(s, 0, 0, new StringBuilder(), result);
    return result;
}
 
private void backtrack(String s, int start, int partCount,
                        StringBuilder path, List<String> result) {
    // 结束条件：恰好分了 4 段，且处理完了整个字符串
    if (partCount == 4) {
        if (start == s.length()) {
            result.add(path.toString());
        }
        return;
    }
 
    // 每段长度为 1-3
    for (int len = 1; len <= 3; len++) {
        if (start + len > s.length()) break;  // 越界
 
        String segment = s.substring(start, start + len);
 
        // 前向约束检查
        if (!isValidSegment(segment)) continue;
 
        // 做选择
        int prevLen = path.length();
        if (partCount > 0) path.append('.');  // 不是第一段，加点
        path.append(segment);
 
        backtrack(s, start + len, partCount + 1, path, result);
 
        // 回溯（恢复到 prevLen）
        path.setLength(prevLen);
    }
}
 
private boolean isValidSegment(String seg) {
    if (seg.length() > 1 && seg.charAt(0) == '0') return false;  // 前导零
    int val = Integer.parseInt(seg);
    return val <= 255;
}

4.4 逐步模拟

s = "25525511135"：

backtrack(start=0, part=0)
  len=1: "2" 合法 → "2"
    backtrack(start=1, part=1)
      len=1: "5" → "2.5"
        ... (后续拼不成4段完整IP，剪枝)
      ...
  len=2: "25" 合法 → "25"
    backtrack(start=2, part=1)
      len=1: "5" → "25.5"
        ...
      len=2: "52" → "25.52"
        ...
      len=3: "525" → "25.525"（>255，不合法，跳过）
  len=3: "255" 合法 → "255"
    backtrack(start=3, part=1)
      len=1: "2" → "255.2"
        ...
      len=2: "25" → "255.25"
        ...
      len=3: "255" 合法 → "255.255"
        backtrack(start=6, part=2)
          len=1: "1" → "255.255.1"
            backtrack(start=7, part=3)
              len=1: "1" → "255.255.1.1" → start=8 ≠ 11，不收集
              len=2: "11" → "255.255.1.11" → start=9 ≠ 11，不收集
              len=3: "113" → "255.255.1.113" → start=10 ≠ 11，不收集
              （等等，还有 "135"）
              其实 start=7 时长度 = 11-7=4，可选 1,2,3 位
              len=4: 超过3，break
          len=2: "11" → "255.255.11"
            backtrack(start=8, part=3)
              len=1: "1" → start=9 ≠ 11
              len=2: "13" → start=10 ≠ 11
              len=3: "135" 合法 → "255.255.11.135" → start=11==11，收集！✅
          len=3: "111" 合法 → "255.255.111"
            backtrack(start=9, part=3)
              len=1: "3" → start=10 ≠ 11
              len=2: "35" 合法 → "255.255.111.35" → start=11==11，收集！✅
              len=3: "135"（>255，剪枝）... 实际"135">255

结果：["255.255.11.135","255.255.111.35"] ✅

4.5 额外剪枝：提前过滤不可能的情况

// 每段长度 1-3，共 4 段 → 字符串长度必须在 [4, 12]
if (s.length() < 4 || s.length() > 12) return result;
 
// 每次递归时，检查剩余字符和剩余段数是否匹配
int remaining = s.length() - start;
int segLeft = 4 - partCount;
// 每段至少 1 字符，至多 3 字符
if (remaining < segLeft || remaining > segLeft * 3) return;

这个剪枝在字符串较长或较短时大幅减少搜索空间。

第 5 章三道题的横向对比

维度	Palindrome Partitioning	Generate Parentheses	Restore IP Addresses
搜索树每层	选切割点（1 到 n）	选 `(` 或 `)`	选段长（1 到 3）
结束条件	处理完整字符串	路径长 = 2n	4 段且处理完字符串
合法性约束	是否回文	open/close 数量平衡	0-255，无前导零
剪枝方式	非回文跳过	不满足约束时不进入分支	越界/超范围/前导零跳过
状态参数	start 指针	open, close 计数	start + partCount

共同模式：

使用 start（或等价的指针/计数器）跟踪”当前处理到哪里”
在每次”做选择”前，先检查合法性（前向约束）
结束条件检查”是否处理完全”（而不只是”路径长度”）

第 6 章面试技巧

6.1 字符串回溯的通用答题框架

1. 明确"切割点/选择点"是什么：字符串的每个位置？特定字符的选择？
2. 明确"每段"的合法性条件（这就是剪枝的依据）
3. 明确"结束条件"：处理完整字符串？路径满足特定长度？
4. 套用通用框架：start 指针推进，合法性前向检查，递归 + 回溯

6.2 StringBuilder vs String 的选择

在回溯中，路径记录常用两种方式：

List<String> + path.add(segment) / path.remove()：适合分割问题（每次选一个子串）
StringBuilder + path.append(c) / path.deleteCharAt(len-1)：适合逐字符构建的问题（括号生成、IP 地址）

StringBuilder 的回溯（deleteCharAt 或 setLength(prevLen)）比 String 的创建开销小，推荐在逐字符构建时使用。

本章小结

字符串型回溯的三道题展示了一个共同的设计哲学：用约束作为剪枝，让搜索树只展开合法的分支。

Palindrome Partitioning：切割点的选择 + 回文性前向检查 + DP 预处理优化
Generate Parentheses：两个有约束的选择 + 括号平衡约束传播（无需显式回溯路径）
Restore IP Addresses：段长选择 + 三重约束（长度、前导零、数值范围）

下一篇文章进入棋盘型回溯——N-Queens 和 Sudoku Solver，这类问题的约束更复杂，需要维护行列对角线等多个状态，剪枝效果也更显著。

关联文章：组合型回溯：Combination Sum 系列与去重艺术 | 棋盘型回溯：N-Queens 与数独求解

汀的知识碎片

文章导航

07 字符串型回溯：分割、括号生成与 IP 地址恢复

字符串型回溯：分割、括号生成与 IP 地址恢复

摘要

第 1 章字符串回溯的通用模型

1.1 从”选元素”到”选切割点”

1.2 字符串回溯的通用框架

第 2 章 LeetCode 131：Palindrome Partitioning

2.1 题目

2.2 核心实现

2.3 优化：预处理回文 DP

2.4 搜索树模拟

第 3 章 LeetCode 22：Generate Parentheses

3.1 题目

3.2 括号合法性的状态约束

3.3 实现

3.4 搜索树（n=2）

3.5 有效约束 vs 暴力生成再过滤

第 4 章 LeetCode 93：Restore IP Addresses

4.1 题目

4.2 IP 地址的结构约束

4.3 实现

4.4 逐步模拟

4.5 额外剪枝：提前过滤不可能的情况

第 5 章三道题的横向对比

第 6 章面试技巧

6.1 字符串回溯的通用答题框架

6.2 StringBuilder vs String 的选择

本章小结

On this page

汀的知识碎片

文章导航

07 字符串型回溯：分割、括号生成与 IP 地址恢复

字符串型回溯：分割、括号生成与 IP 地址恢复

摘要

第 1 章 字符串回溯的通用模型

1.1 从”选元素”到”选切割点”

1.2 字符串回溯的通用框架

第 2 章 LeetCode 131：Palindrome Partitioning

2.1 题目

2.2 核心实现

2.3 优化：预处理回文 DP

2.4 搜索树模拟

第 3 章 LeetCode 22：Generate Parentheses

3.1 题目

3.2 括号合法性的状态约束

3.3 实现

3.4 搜索树（n=2）

3.5 有效约束 vs 暴力生成再过滤

第 4 章 LeetCode 93：Restore IP Addresses

4.1 题目

4.2 IP 地址的结构约束

4.3 实现

4.4 逐步模拟

4.5 额外剪枝：提前过滤不可能的情况

第 5 章 三道题的横向对比

第 6 章 面试技巧

6.1 字符串回溯的通用答题框架

6.2 StringBuilder vs String 的选择

本章小结

On this page

第 1 章字符串回溯的通用模型

第 5 章三道题的横向对比

第 6 章面试技巧