回文字符串寻找 #

1. 回文字符串寻找问题的介绍
2. 回文字符串寻找的算法分析
3. 回文字符串寻找代码实现

回文字符串寻找问题的介绍 #

给定字符串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")

小结 #

• 根据回文字符串寻找，理解回溯算法在限定子集问题中的应用
• 掌握回文字符串寻找求解的回溯算法

习题 #

1. 上述问题中递归的深度仅为2，因此理论上可以通过一个两重循环去解决它，请尝试解决？
2. 如果将该问题改变为回文字符串的分割问题，即将字符串分割成的子串都是回文字符串，请用回溯的方法解决它