131. 分割回文串(Medium)
# 题目描述
给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。返回 s 所有可能的分割方案。
# 样例
Input: "aab"
Output:
[
["aa","b"],
["a","a","b"]
]
1
2
3
4
5
6
2
3
4
5
6
# 题目解析
# 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
编辑 (opens new window)
上次更新: 2022/10/25, 02:40:54