1.问题描述
2.做题思路(关键是画出对于的二叉树图)
1.思考从起始串的分割方案, 有a ,aa, aab三种方式
2.————————————剩余ab,b,空
(接下来对ab,b同样的方式进行分割)
3.———————对ab分割有a, ab
, 对b分割只有b
3.代码实现
path = [] # 收集路径上的回文串
result = [] # 统计结果
def isHW(s, start, end): # 判断串是否是回文串(顺序读或倒序读结果一样)
while start <= end:
if s[start] == s[end]:
start += 1
end -= 1
else:
return False
return True
def backtracking(s, startIndex):
if statIndex >= len(s):
result.append(path[:])
return
for i in range(startIndex. len(s)):
if isHW(s, startIndex, i): # 符合回文串才继续向下递归
path.append(s[startIndex:i+1])
backtracking(s, i+1) # 见图片理解为什么是i+1
path.pop()
backtracking(s, 0)
print(result)