解决回溯算法之切割问题(leetcode--分割回文串)

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)