https://leetcode.com/problems/palindrome-partitioning
131. Palindrome Partitioning
回传所有可以拆成数个子字串且全是回文的组合
Example 1:
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
Example 2:
Input: s = "a"
Output: [["a"]]
思路:
1.确认子字串是否为回文
2.backtracking
Python Code:
class Solution:
def partition(self, s: str) -> List[List[str]]:
def is_palindrome(l, r):
while l < r:
if s[l] != s[r]:
return False
l += 1
r -= 1
return True
def backtrack(start, path):
if start == len(s):
res.append(path[:])
return
for end in range(start, len(s)):
if is_palindrome(start, end):
path.append(s[start:end + 1])
backtrack(end + 1, path)
path.pop()
res = []
backtrack(0, [])
return res