LeetCode 131中等回溯 · 切割

分割回文串图解题解

这道题到底在问什么

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

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

先想最直接的笨办法

记住这条：枚举切点 → 前缀是回文才往下切 → 切到末尾收集一种方案。下面逐帧看它怎么跑。（动画第 3 步）

最优解：一步一步想明白

3记住这条：枚举切点 → 前缀是回文才往下切 → 切到末尾收集一种方案。下面逐帧看它怎么跑。
4从下标 0 起试切前缀 "a"（切到下标 0）：它正着倒着都一样，是回文 ✓。切下它放进 path → ["a"]，再去切剩下的 "abb"。
5从下标 1 起试切前缀 "a"（切到下标 1）：它正着倒着都一样，是回文 ✓。切下它放进 path → ["a","a"]，再去切剩下的 "bb"。
6从下标 2 起试切前缀 "b"（切到下标 2）：它正着倒着都一样，是回文 ✓。切下它放进 path → ["a","a","b"]，再去切剩下的 "b"。
7从下标 3 起试切前缀 "b"（切到下标 3）：它正着倒着都一样，是回文 ✓。切下它放进 path → ["a","a","b","b"]，再去切剩下的 "（空）"。
8start 已经走到串尾，全部字符都切完了——当前 path=["a","a","b","b"] 就是一种完整的分割，收进结果（第 1 种）。
9"b" 这条分支已经探完，撤销它（path 弹出），回到 ["a","a","b"]，让 start 复位去试更长的前缀。
10"b" 这条分支已经探完，撤销它（path 弹出），回到 ["a","a"]，让 start 复位去试更长的前缀。
11从下标 2 起试切前缀 "bb"（切到下标 3）：它正着倒着都一样，是回文 ✓。切下它放进 path → ["a","a","bb"]，再去切剩下的 "（空）"。
12start 已经走到串尾，全部字符都切完了——当前 path=["a","a","bb"] 就是一种完整的分割，收进结果（第 2 种）。
13"bb" 这条分支已经探完，撤销它（path 弹出），回到 ["a","a"]，让 start 复位去试更长的前缀。
14"a" 这条分支已经探完，撤销它（path 弹出），回到 ["a"]，让 start 复位去试更长的前缀。
15从下标 1 起试切前缀 "ab"（切到下标 2）：首尾字符不同，不是回文 ✗。剪掉这条分支——前缀都不合法就没必要再切后面的了。
16从下标 1 起试切前缀 "abb"（切到下标 3）：首尾字符不同，不是回文 ✗。剪掉这条分支——前缀都不合法就没必要再切后面的了。
17"a" 这条分支已经探完，撤销它（path 弹出），回到 [空]，让 start 复位去试更长的前缀。
18从下标 0 起试切前缀 "aa"（切到下标 1）：它正着倒着都一样，是回文 ✓。切下它放进 path → ["aa"]，再去切剩下的 "bb"。
19从下标 2 起试切前缀 "b"（切到下标 2）：它正着倒着都一样，是回文 ✓。切下它放进 path → ["aa","b"]，再去切剩下的 "b"。
20从下标 3 起试切前缀 "b"（切到下标 3）：它正着倒着都一样，是回文 ✓。切下它放进 path → ["aa","b","b"]，再去切剩下的 "（空）"。
21start 已经走到串尾，全部字符都切完了——当前 path=["aa","b","b"] 就是一种完整的分割，收进结果（第 3 种）。
22"b" 这条分支已经探完，撤销它（path 弹出），回到 ["aa","b"]，让 start 复位去试更长的前缀。
23"b" 这条分支已经探完，撤销它（path 弹出），回到 ["aa"]，让 start 复位去试更长的前缀。
24从下标 2 起试切前缀 "bb"（切到下标 3）：它正着倒着都一样，是回文 ✓。切下它放进 path → ["aa","bb"]，再去切剩下的 "（空）"。
25start 已经走到串尾，全部字符都切完了——当前 path=["aa","bb"] 就是一种完整的分割，收进结果（第 4 种）。
26"bb" 这条分支已经探完，撤销它（path 弹出），回到 ["aa"]，让 start 复位去试更长的前缀。
27"aa" 这条分支已经探完，撤销它（path 弹出），回到 [空]，让 start 复位去试更长的前缀。
28从下标 0 起试切前缀 "aab"（切到下标 2）：首尾字符不同，不是回文 ✗。剪掉这条分支——前缀都不合法就没必要再切后面的了。
29从下标 0 起试切前缀 "aabb"（切到下标 3）：首尾字符不同，不是回文 ✗。剪掉这条分支——前缀都不合法就没必要再切后面的了。

⚠️ 容易写错的地方

✗ 错：res.append(path)

✓ 对：res.append(path[:]) / new ArrayList<>(path)

path 是同一个引用，后面 pop 会改掉已存方案，必须存副本

✗ 错：不判回文就往下切

✓ 对：isPal(sub) 为真才递归

回文剪枝是核心：前缀不合法就没必要切剩余，省掉大量无效分支

✗ 错：sub = s[start:end]

✓ 对：sub = s[start:end+1]

切片右开区间，要含 end 这个字符必须 +1，否则漏掉末尾字符

完整代码（Python / C++ / Java）

Python

def partition(s):
    res = []
    def isPal(t):
        return t == t[::-1]              # 正反相同即回文
    def backtrack(start, path):
        if start == len(s):
            res.append(path[:])           # 切到末尾，收集一种分割
            return
        for end in range(start, len(s)):
            sub = s[start:end + 1]        # 试切前缀 s[start..end]
            if isPal(sub):                # 是回文才继续切剩余
                path.append(sub)
                backtrack(end + 1, path)
                path.pop()                # 撤销，回溯
    backtrack(0, [])
    return res

C++

vector<vector<string>> partition(string s){
    vector<vector<string>> res; vector<string> path;
    auto isPal = [](const string& t){
        for(int i=0,j=t.size()-1;i<j;i++,j--) if(t[i]!=t[j]) return false;
        return true;
    };
    function<void(int)> bt = [&](int start){
        if(start == (int)s.size()){ res.push_back(path); return; }
        for(int end=start; end<(int)s.size(); ++end){
            string sub = s.substr(start, end-start+1);
            if(isPal(sub)){               // 前缀是回文才往下切
                path.push_back(sub);
                bt(end + 1);
                path.pop_back();          // 撤销
            }
        }
    };
    bt(0); return res;
}

Java

public List<List<String>> partition(String s){
    List<List<String>> res = new ArrayList<>();
    backtrack(s, 0, new ArrayList<>(), res);
    return res;
}
private boolean isPal(String t){
    for(int i = 0, j = t.length() - 1; i < j; i++, j--)
        if(t.charAt(i) != t.charAt(j)) return false;
    return true;
}
private void backtrack(String s, int start, List<String> path, List<List<String>> res){
    if(start == s.length()){ res.add(new ArrayList<>(path)); return; }
    for(int end = start; end < s.length(); end++){
        String sub = s.substring(start, end + 1);
        if(isPal(sub)){                  // 前缀是回文才继续
            path.add(sub);
            backtrack(s, end + 1, path, res);
            path.remove(path.size() - 1); // 撤销，回溯
        }
    }
}

复杂度

时间

O(n·2ⁿ)

n-1 个切点各切或不切共 2ⁿ⁻¹ 种，每种判回文 + 复制 O(n)

空间

O(n)

递归深度 + path 长度，不计结果存储

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着分割回文串的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

每次都重新判回文会不会很慢？怎么优化？+

可以预处理一张 dp[i][j] 表，O(n²) 先算好「s[i..j] 是否回文」，回溯里 O(1) 查表，避免每次切都重新扫一遍子串。

如果只问「最少切几刀」（LC132）呢？+

那是 DP 题：dp[i]=前 i 个字符的最少切割数，结合回文表转移，不需要枚举所有方案，O(n²)。

想听吴师兄把这道题讲给你听？

文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把分割回文串一步步讲透（全站已上线 905 份讲透，持续扩充），卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。

了解年卡方案 →先去动画页看完整样板 →

把这道题真正拿下

看动画图解 →分割回文串交互动画,逐步看清每一步怎么走

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

LeetCode 131中等回溯 · 切割

分割回文串图解题解

这道题到底在问什么

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

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

先想最直接的笨办法

记住这条：枚举切点 → 前缀是回文才往下切 → 切到末尾收集一种方案。下面逐帧看它怎么跑。（动画第 3 步）

最优解：一步一步想明白

3记住这条：枚举切点 → 前缀是回文才往下切 → 切到末尾收集一种方案。下面逐帧看它怎么跑。
4从下标 0 起试切前缀 "a"（切到下标 0）：它正着倒着都一样，是回文 ✓。切下它放进 path → ["a"]，再去切剩下的 "abb"。
5从下标 1 起试切前缀 "a"（切到下标 1）：它正着倒着都一样，是回文 ✓。切下它放进 path → ["a","a"]，再去切剩下的 "bb"。
6从下标 2 起试切前缀 "b"（切到下标 2）：它正着倒着都一样，是回文 ✓。切下它放进 path → ["a","a","b"]，再去切剩下的 "b"。
7从下标 3 起试切前缀 "b"（切到下标 3）：它正着倒着都一样，是回文 ✓。切下它放进 path → ["a","a","b","b"]，再去切剩下的 "（空）"。
8start 已经走到串尾，全部字符都切完了——当前 path=["a","a","b","b"] 就是一种完整的分割，收进结果（第 1 种）。
9"b" 这条分支已经探完，撤销它（path 弹出），回到 ["a","a","b"]，让 start 复位去试更长的前缀。
10"b" 这条分支已经探完，撤销它（path 弹出），回到 ["a","a"]，让 start 复位去试更长的前缀。
11从下标 2 起试切前缀 "bb"（切到下标 3）：它正着倒着都一样，是回文 ✓。切下它放进 path → ["a","a","bb"]，再去切剩下的 "（空）"。
12start 已经走到串尾，全部字符都切完了——当前 path=["a","a","bb"] 就是一种完整的分割，收进结果（第 2 种）。
13"bb" 这条分支已经探完，撤销它（path 弹出），回到 ["a","a"]，让 start 复位去试更长的前缀。
14"a" 这条分支已经探完，撤销它（path 弹出），回到 ["a"]，让 start 复位去试更长的前缀。
15从下标 1 起试切前缀 "ab"（切到下标 2）：首尾字符不同，不是回文 ✗。剪掉这条分支——前缀都不合法就没必要再切后面的了。
16从下标 1 起试切前缀 "abb"（切到下标 3）：首尾字符不同，不是回文 ✗。剪掉这条分支——前缀都不合法就没必要再切后面的了。
17"a" 这条分支已经探完，撤销它（path 弹出），回到 [空]，让 start 复位去试更长的前缀。
18从下标 0 起试切前缀 "aa"（切到下标 1）：它正着倒着都一样，是回文 ✓。切下它放进 path → ["aa"]，再去切剩下的 "bb"。
19从下标 2 起试切前缀 "b"（切到下标 2）：它正着倒着都一样，是回文 ✓。切下它放进 path → ["aa","b"]，再去切剩下的 "b"。
20从下标 3 起试切前缀 "b"（切到下标 3）：它正着倒着都一样，是回文 ✓。切下它放进 path → ["aa","b","b"]，再去切剩下的 "（空）"。
21start 已经走到串尾，全部字符都切完了——当前 path=["aa","b","b"] 就是一种完整的分割，收进结果（第 3 种）。
22"b" 这条分支已经探完，撤销它（path 弹出），回到 ["aa","b"]，让 start 复位去试更长的前缀。
23"b" 这条分支已经探完，撤销它（path 弹出），回到 ["aa"]，让 start 复位去试更长的前缀。
24从下标 2 起试切前缀 "bb"（切到下标 3）：它正着倒着都一样，是回文 ✓。切下它放进 path → ["aa","bb"]，再去切剩下的 "（空）"。
25start 已经走到串尾，全部字符都切完了——当前 path=["aa","bb"] 就是一种完整的分割，收进结果（第 4 种）。
26"bb" 这条分支已经探完，撤销它（path 弹出），回到 ["aa"]，让 start 复位去试更长的前缀。
27"aa" 这条分支已经探完，撤销它（path 弹出），回到 [空]，让 start 复位去试更长的前缀。
28从下标 0 起试切前缀 "aab"（切到下标 2）：首尾字符不同，不是回文 ✗。剪掉这条分支——前缀都不合法就没必要再切后面的了。
29从下标 0 起试切前缀 "aabb"（切到下标 3）：首尾字符不同，不是回文 ✗。剪掉这条分支——前缀都不合法就没必要再切后面的了。

⚠️ 容易写错的地方

✗ 错：res.append(path)

✓ 对：res.append(path[:]) / new ArrayList<>(path)

path 是同一个引用，后面 pop 会改掉已存方案，必须存副本

✗ 错：不判回文就往下切

✓ 对：isPal(sub) 为真才递归

回文剪枝是核心：前缀不合法就没必要切剩余，省掉大量无效分支

✗ 错：sub = s[start:end]

✓ 对：sub = s[start:end+1]

切片右开区间，要含 end 这个字符必须 +1，否则漏掉末尾字符

完整代码（Python / C++ / Java）

Python

def partition(s):
    res = []
    def isPal(t):
        return t == t[::-1]              # 正反相同即回文
    def backtrack(start, path):
        if start == len(s):
            res.append(path[:])           # 切到末尾，收集一种分割
            return
        for end in range(start, len(s)):
            sub = s[start:end + 1]        # 试切前缀 s[start..end]
            if isPal(sub):                # 是回文才继续切剩余
                path.append(sub)
                backtrack(end + 1, path)
                path.pop()                # 撤销，回溯
    backtrack(0, [])
    return res

C++

vector<vector<string>> partition(string s){
    vector<vector<string>> res; vector<string> path;
    auto isPal = [](const string& t){
        for(int i=0,j=t.size()-1;i<j;i++,j--) if(t[i]!=t[j]) return false;
        return true;
    };
    function<void(int)> bt = [&](int start){
        if(start == (int)s.size()){ res.push_back(path); return; }
        for(int end=start; end<(int)s.size(); ++end){
            string sub = s.substr(start, end-start+1);
            if(isPal(sub)){               // 前缀是回文才往下切
                path.push_back(sub);
                bt(end + 1);
                path.pop_back();          // 撤销
            }
        }
    };
    bt(0); return res;
}

Java

public List<List<String>> partition(String s){
    List<List<String>> res = new ArrayList<>();
    backtrack(s, 0, new ArrayList<>(), res);
    return res;
}
private boolean isPal(String t){
    for(int i = 0, j = t.length() - 1; i < j; i++, j--)
        if(t.charAt(i) != t.charAt(j)) return false;
    return true;
}
private void backtrack(String s, int start, List<String> path, List<List<String>> res){
    if(start == s.length()){ res.add(new ArrayList<>(path)); return; }
    for(int end = start; end < s.length(); end++){
        String sub = s.substring(start, end + 1);
        if(isPal(sub)){                  // 前缀是回文才继续
            path.add(sub);
            backtrack(s, end + 1, path, res);
            path.remove(path.size() - 1); // 撤销，回溯
        }
    }
}

复杂度

时间

O(n·2ⁿ)

n-1 个切点各切或不切共 2ⁿ⁻¹ 种，每种判回文 + 复制 O(n)

空间

O(n)

递归深度 + path 长度，不计结果存储

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着分割回文串的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

每次都重新判回文会不会很慢？怎么优化？+

可以预处理一张 dp[i][j] 表，O(n²) 先算好「s[i..j] 是否回文」，回溯里 O(1) 查表，避免每次切都重新扫一遍子串。

如果只问「最少切几刀」（LC132）呢？+

那是 DP 题：dp[i]=前 i 个字符的最少切割数，结合回文表转移，不需要枚举所有方案，O(n²)。

想听吴师兄把这道题讲给你听？

了解年卡方案 →先去动画页看完整样板 →

把这道题真正拿下

看动画图解 →分割回文串交互动画,逐步看清每一步怎么走

分割回文串 图解题解

这道题到底在问什么

先想最直接的笨办法

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

分割回文串 图解题解

这道题到底在问什么

先想最直接的笨办法

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

分割回文串图解题解

分割回文串图解题解