131. 分割回文串(Medium)

题目描述

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

样例

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

题目解析

参考： 回溯算法：分割回文串

Python 示例

    def backtracking(s, ans, startIndex, tmp):
        if startIndex >= len(s):
            ans.append(tmp[:])
        
        for i in range(startIndex, len(s)):
            if isValid(s[startIndex: i + 1]):
                tmp.append(s[startIndex: i + 1]) # 切割
                backtracking(s, ans, i + 1, tmp) 
                tmp.pop()
        
    def isValid(s):
        """ 验证是否是回文字符串 """
        i, j = 0, len(s) - 1
        while i < j:
            if s[i] != s[j]:
                return False 
            i += 1
            j -= 1
        return True 

    class Solution:
        def partition(self, s: str) -> List[List[str]]:
            ans = []
            backtracking(s, ans, 0, [])
            return ans