回文字符串寻找
- 回文字符串寻找问题的介绍
- 回文字符串寻找的算法分析
- 回文字符串寻找代码实现
回文字符串寻找问题的介绍
给定字符串s,寻找字符串中所有的回文字符串，回文字符串的寻找本质上是子集问题，例如字符串str="12321"的回文字符串寻找，
就是从集合{0,1,2,3,4}中选取两个数字来作为子串的索引,来找出子串中所有的回文字符串
str[0,1]="1"
str[0,5]="12321"
str[1,2]="2"
str[1,4]="232"
str[2,3]="3"
str[3,4]="2"
str[4,5]="1"
回文字符串寻找的算法分析
第一步:从集合{0,1,2,3……len(str)}中选一数做为字符串的初始索引
第二步:从集合{0,1,2,3……len(str)}中选一个不小于第一步数作为结束索引，判断子串是否为回文字符串，如果是输出。
回文字符串寻找的代码实现
def ispalindrome(s):#判断是否是回文字符串
return s==s[::-1]
res=[0]#保存res[step]的结果
def dfs(step,s):
if(step>2):#仅需两部即可完成一次选择
if(ispalindrome(s[res[1]:res[2]+1])):
print("str[{},{}]=".format(res[1],res[2]+1),s[res[1]:res[2]+1])
return
for i in range(0,len(s)):#每次选择一个可能的索引值
if(i>=res[step-1]):#每次选择的索引值不小于上一次
res.append(i)#保存结果
dfs(step+1,s)
res.pop()#撤销上一次的选择
dfs(1,"12321")
小结
- 根据回文字符串寻找，理解回溯算法在限定子集问题中的应用
- 掌握回文字符串寻找求解的回溯算法
习题
- 上述问题中递归的深度仅为2，因此理论上可以通过一个两重循环去解决它，请尝试解决？
- 如果将该问题改变为回文字符串的分割问题，即将字符串分割成的子串都是回文字符串，请用回溯的方法解决它