寻找最长回文字符串

小灰灰 2023-03-13 05:10 23阅读 0赞

## 定义： ##

回文字符串是将字符串逆序后和原字符串一样的字符串，就是正着读和反着读都一样的字符串。

## 基本思路： ##

给定一个字符串，寻找它的回文字符串，我的实现思路是使用回溯法，具体如下：首先选定一个点，使用两个变量left和right分别指向该点的左右两侧，如果left和right指向的字符串相等，那么left向左移动一位，right向右移动一位，继续判断，直到left和right不相等，此时left和right所组成的字符串就是回文字符串，判断回文字符串长度，如果大于result,就更换result的值，否则不更换。按照这个想法，循环迭代每一个点。

注意事项：上述方法中，当我们选定一个点以后，默认就以这个点为回文字符串的中心，但是如果这个回文字符串字符个数为偶数个，例如"bcaacd"字符串，上述方法则不可行，此时我们应选定两个紧邻的字符为中心。

## 实现代码： ##

def longsPairs(s):
        length = len(s)
        result = str()     # 记录最终结果字符串
        
        if length == 1 or length == 0:
            return s
            
        for pos in range(0, length - 1):    # 开始迭代每一个点
            start = pos           # start指向pos左方向
            end = pos			  # end指向pos右方向
            while s[start] == s[end]:
                start -= 1
                end += 1
                if start < 0 or end >= length:   # 越界则退出循环
                    break
            if len(result) < end - start - 1:    # 如果此时回文字符串长度大于result的长度，则更新result的值
                start += 1
                result = s[start:end]
                
            start = pos - 1
            end = pos + 1
            if s[end] == s[pos]:    # 解决“注意事项”中的问题，如果此时end和pos指向的字符相等，那么该回文字符串长度为偶数
                end += 1
            while start > -1 and end < length and s[start] == s[end]:
                start -= 1
                end += 1
            if len(result) < end - start - 1:
                start += 1
                result = s[start:end]
        return result