图解分割回文串：用"积木游戏"巧解难题！

大家好，我是忍者算法。今天我们来挑战一道非常有趣的题目 - LeetCode 131「分割回文串」。这道题乍看有点复杂，但用我们小时候玩积木的思维来理解，你会发现它其实非常有意思！

🎮 妙趣横生的童年回忆

还记得小时候玩积木吗？我们经常需要把一根长积木切分成不同的小块，每个小块都要符合某种特定的规则。今天的算法题就像是在玩一个特殊的积木游戏：我们要把一个字符串切分成若干小段，每一段都必须是回文串。

比如"aab"这个积木，我们可以这样切：

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

是不是一下子觉得亲切了很多？

💡 问题本质探索

题目要求： 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回所有可能的分割方案。

让我们看个具体例子：

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

🤔 解题之前的思考

想象我们面对一个积木（字符串），需要考虑以下几个关键问题：

1. 在哪里可以切？

   • 理论上每个字符之间都可以切
   • 但切完的每一段都必须是回文串

2. 切还是不切？

   • 在每个可能的切割点，我们都面临"切"或"不切"的选择
   • 这暗示了我们可能需要用回溯算法来尝试所有可能性

🚀 积木切割大法

核心思路：回溯 + 动态规划优化

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        // dp数组用于优化回文串判断
        boolean[][] dp = new boolean[s.length()][s.length()];
        // 预处理所有可能的回文子串
        for(int len = 1; len <= s.length(); len++) {
            for(int i = 0; i <= s.length() - len; i++) {
                int j = i + len - 1;
                // 长度为1的子串一定是回文
                if(len == 1) {
                    dp[i][j] = true;
                }
                // 长度为2的子串，两个字符相等即为回文
                else if(len == 2) {
                    dp[i][j] = s.charAt(i) == s.charAt(j);
                }
                // 长度大于2的子串，首尾字符相等且中间是回文串
                else {
                    dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i+1][j-1];
                }
            }
        }
        
        backtrack(s, 0, new ArrayList<>(), result, dp);
        return result;
    }
    
    private void backtrack(String s, int start, List<String> current, 
                          List<List<String>> result, boolean[][] dp) {
        // 到达字符串末尾，说明找到一个有效方案
        if (start >= s.length()) {
            result.add(new ArrayList<>(current));
            return;
        }
        
        // 尝试不同的切割长度
        for (int end = start; end < s.length(); end++) {
            // 如果当前子串是回文串，继续递归
            if (dp[start][end]) {
                current.add(s.substring(start, end + 1));
                backtrack(s, end + 1, current, result, dp);
                current.remove(current.size() - 1);  // 回溯，撤销选择
            }
        }
    }
}

代码解释

就像玩积木时我们会：

1. 先观察每段积木是否符合要求（使用dp数组预处理所有回文子串）
2. 从起点开始，尝试不同的切割位置（回溯过程）
3. 记录所有符合要求的切割方案（result列表）

🎯 难点突破

1. 回文串判断优化

很多同学一开始都用暴力方法判断回文串，导致效率很低。使用动态规划预处理所有可能的回文子串，可以大大提高效率：

• dp[i][j] 表示 s[i..j] 是否为回文串
• 状态转移：dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]

2. 回溯过程处理

在每个位置，我们都面临"切"还是"不切"的选择：

• 如果切，当前子串必须是回文串
• 切完后，对剩余的字符串继续进行分割
• 记得在回溯时撤销选择

💡 优化思路

1. 空间优化：

   • 可以使用滚动数组优化dp数组的空间
   • 如果内存要求特别严格，可以用中心扩展法代替dp数组

2. 剪枝优化：

   • 如果发现剩余字符无法构成回文串，可以提前返回
   • 可以记录最长回文子串长度，超过这个长度就不用尝试

🔄 相似题目推荐

• 分割回文串 II（LeetCode 132）
• 回文子串（LeetCode 647）
• 最长回文子串（LeetCode 5）

这些题目都围绕着回文串的特性，掌握了今天的题目，相信你对这些题目也会有新的认识！

---

作者：忍者算法 公众号：忍者算法

🎁 回复【刷题清单】获取LeetCode高频面试题合集 🧑‍💻 回复【代码】获取多语言完整题解 💡 回复【加群】加入算法交流群，一起进步

#算法面试 #LeetCode #回溯算法 #动态规划