动态规划之最长回文子串

傷城~ 2023-08-17 17:32 114阅读 0赞

思路：

这类问题通过穷举的办法，判断是否是回文子串并再筛选出最长的，效率很差。使用动态规划的策略来求解，首先从子问题入手，并将子问题的解保存起来，然后在求解后面的问题时，反复的利用子问题的解，可以极大的提示效率。

由于最长回文子串是要求连续的，所以可以假设i为子串的起始坐标，j为子串的终点坐标，其中 i 和 j 都是大于等于 0 并且小于字符串长度 length 的，且 i<= j，这样子串的长度就可以使用j -i + 1 表示了。从长度为 1 的子串依次遍历，长度为 1 的子串肯定是回文的，其长度就是 1；然后是长度为 2 的子串依次遍历，只要 str\[i\] 等于 str\[j\] ，它就是回文的，其长度为 2；接下来就好办了，长度大于 2 的子串，如果它要满足是回文子串的性质，就必须有 str\[i\] 等于 str\[j\] ，并且去掉两头的子串 str\[i+1 ... j-1\] 也一定是回文子串，所以我们使用一个数组来保存以 i为子串起始坐标，j为子串终点坐标的子串是否是回文的，由于我们是从子问题依次增大求解的，所以求解 \[i ... j\] 的问题时，比它规模更小的问题结果都是可以直接使用的

# coding=utf8
    
    
    class Solution:
        """
        @param s: input string
        @return: the longest palindromic substring
        """
    
        def longestPalindrome(self, s):
            if not s:
                return ""
    
            n = len(s)
            # 第一维参数表示起始位置坐标，第二维参数表示终点坐标
            # is_palindrome[i][j]表示以i为起始坐标，j为终点坐标是否为回文子串
            is_palindrome = [[False] * n for _ in range(n)]
    
            longest, start, end = 1, 0, 0
            for j in range(n):
                for i in range(j+1):
                    if j - i < 2:
                        # 子字符串长度小于 2 的时候单独处理
                        is_palindrome[i][j] = s[i] == s[j]
                    else:
                        # 如果 [j, i] 是回文子串，那么一定有 [i+1, j-1] 也是回子串
                        is_palindrome[i][j] = (s[i] == s[j] and is_palindrome[i + 1][j - 1])
                    if is_palindrome[i][j] and (j-i + 1 > longest):
                        longest = j-i + 1
                        start, end = i, j
    
            return s[start:end + 1]

参考：  
1、 [https://blog.csdn.net/afei\_\_/article/details/83214042][https_blog.csdn.net_afei_article_details_83214042]  
2、[https://blog.csdn.net/u013309870/article/details/75193592][https_blog.csdn.net_u013309870_article_details_75193592]

转载于:https://www.cnblogs.com/nerrissa/p/11399242.html

[https_blog.csdn.net_afei_article_details_83214042]: https://blog.csdn.net/afei__/article/details/83214042
[https_blog.csdn.net_u013309870_article_details_75193592]: https://blog.csdn.net/u013309870/article/details/75193592