分割回文串 图解题解

这道题到底在问什么

s

"aab"

输出

[["a","a","b"],["aa","b"]]

先想最直接的笨办法

把 "aab" 切成若干段，每段都是回文。从位置 0 开始枚举：当前段先试最短 s[0..0]='a'。（动画第 4 步）

最优解：一步一步想明白

1. 3关键不是背模板，而是看懂为什么这题适合回溯 · 切割。
2. 4把 "aab" 切成若干段，每段都是回文。从位置 0 开始枚举：当前段先试最短 s[0..0]='a'。
3. 5单字符天然回文 ✓ → 切下第一段 [a]，递归处理剩下的 "ab"。
4. 6绿色=已切下的段。在剩余里试 s[1]='a'，回文 ✓ → 切下 [a,a]，剩 "b"。
5. 7试 s[2]='b'，回文 ✓，切到末尾 → 收集第一种方案 [a, a, b]。
6. 8回溯到只切了 [a]。试更长的段 s[1..2]='ab'(蓝框)：左端 a、右端 b 不相等 → 不是回文 → 跳过这个切点。
7. 9回到最开头，试更长的前缀 s[0..1]='aa'：左右两端都是 a 相等 → 是回文 → 切下 [aa]，剩 "b"。
8. 10剩下的 'b' 回文 ✓ → 收集第二种方案 [aa, b]。
9. 11整串 "aab" 试 "aab" 也非回文(a≠b)→跳过。最终 2 种切法：[[a,a,b],[aa,b]]，每段都是回文。
10. 14把这句话记住，下次遇到同类题，就能更快选出方向。

⚠️ 容易写错的地方

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

class Solution:
    def partition(self, s):
        ans = []
        def is_pal(l, r):
            while l < r:
                if s[l] != s[r]: return False
                l += 1; r -= 1
            return True
        def backtrack(start, path):
            if start == len(s):
                ans.append(path[:]); return
            for end in range(start, len(s)):
                if is_pal(start, end):              # 当前段回文才切
                    path.append(s[start:end+1])
                    backtrack(end + 1, path)
                    path.pop()
        backtrack(0, [])
        return ans

class Solution {
public:
    vector<vector<string>> ans;
    vector<string> path;
    bool isPal(string& s, int l, int r) {
        while (l < r) { if (s[l] != s[r]) return false; l++; r--; }
        return true;
    }
    void backtrack(string& s, int start) {
        if (start == s.size()) { ans.push_back(path); return; }
        for (int end = start; end < s.size(); end++) {
            if (isPal(s, start, end)) {            // 当前段回文才切
                path.push_back(s.substr(start, end - start + 1));
                backtrack(s, end + 1);
                path.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) { backtrack(s, 0); return ans; }
};

class Solution {
    List<List<String>> ans = new ArrayList<>();
    List<String> path = new ArrayList<>();
    boolean isPal(String s, int l, int r) {
        while (l < r) { if (s.charAt(l) != s.charAt(r)) return false; l++; r--; }
        return true;
    }
    void backtrack(String s, int start) {
        if (start == s.length()) { ans.add(new ArrayList<>(path)); return; }
        for (int end = start; end < s.length(); end++) {
            if (isPal(s, start, end)) {            // 当前段回文才切
                path.add(s.substring(start, end + 1));
                backtrack(s, end + 1);
                path.remove(path.size() - 1);
            }
        }
    }
    public List<List<String>> partition(String s) { backtrack(s, 0); return ans; }
}

# 分割回文串骨架 · 枚举切点
def backtrack(start, path):
    if start == len(s): 收集 path; return
    for end in range(start, len(s)):
        if is_pal(s[start:end+1]):       # 当前段是回文才切
            path.append(s[start:end+1])
            backtrack(end + 1, path)
            path.pop()

复杂度

面试官可能追问