[每日一题][找工作第56天][2025-11-17] Leetcode 131. 分割回文串

题目

131. 分割回文串
给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 
示例 1：
输入：s = “aab”
输出：[[“a”,”a”,”b”],[“aa”,”b”]]
示例 2：
输入：s = “a”
输出：[[“a”]]
 
提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

我的代码（Python）

class Solution:
    def checkPalindrome(self, s: str) -> bool:
        return s == s[-1::-1]
    def partition(self, s: str) -> List[List[str]]:
        print(f's: {s}')
        result = []
        if not s:
            return result
        l = len(s)
        for i in range(1, l + 1):
            if self.checkPalindrome(s[0 : i]):
                if i == l:
                    result.append([s])
                else:
                    nextResult = self.partition(s[i:])
                    for nr in nextResult:
                        result.append([s[0 : i]] + nr)
        return result

点评

和这几天的题目方法都类似，典型的递归调用解决。
不过这个代码效率不好，因为每次都比较是否为回文串，有很多重复计算（实现起来倒是方便的）。
官方题解中给出两种方案，一种是直接预处理字符串，把所有子串可能是回文串的先找出来，这样不用每次判断。
第二种记忆化搜索和第一种差不多，不过相当于是用到了再做处理并记录结果，这样可能有一些子串不会被用到，也就没必要一一计算。
这个方向的优化我忽略了。

---

baddif@gmail.com

AI简历优化站

Nonpareil.me：优化简历，助力职场
开源代码

AI求职跟踪器（建设中）

开源代码

主站（建设中）

Nonpareil Me

相关平台

Github Issues / Notion / Blog