【每日一题0824】分割回文子串

:woman_mage:输入一个纯小写英文字母组成的字符串 s ,请编写一个python函数,将 s 分割成一些子串,使得每个子串都是 回文串 (正着读和反着读都一样的字符串) ,返回 s 所有可能的分割方案。

示例:

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

题目难度:中等
题目来源:leetcode 131

from typing import List

def partition(s: str) -> List[List[str]]:
    pass

assert partition("aab") == [["a","a","b"],["aa","b"]]
assert partition("a") == [["a"]]

做不出来网上抄的,解析也没看懂

class Solution(object):
    def partition(self, s):
        self.isPalindrome = lambda s : s == s[::-1]
        res = []
        self.backtrack(s, res, [])
        return res

    def backtrack(self, s, res, path):
        if not s:
            res.append(path)
            return
        for i in range(1, len(s) + 1): #注意起始和结束位置
            if self.isPalindrome(s[:i]):
                self.backtrack(s[i:], res, path + [s[:i]])

关闭