leetcode [131] 分割回文串

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

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

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        def check(s):
            for i in range(len(s) // 2):
                if s[i] != s[-i - 1]:
                    return False
            return True

        ans = []
        for i in range(1, len(s) + 1):
            if check(s[:i]):
                res = self.partition(s[i:])
                for r in res:
                    r.insert(0, s[:i])
                    ans.append(r)
                if len(res) == 0:
                    ans.append([s[:i]])
        return ans