Q5 Longest Palindromic Substring

echobingo

发布于 2018-04-25 17:19:11

7080

发布于 2018-04-25 17:19:11

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example:

Input: "cbbd"
Output: "bb"

解题思路：

最长回文子串，一句话总结：暴力 O(n^3)，改进 O(n^2)，Manacher O(n) 【马拉车算法】。

看到过一篇写马拉车算法比较好的文章：马拉车算法

由于马拉车理解起来比较困难，这里提出两种 O(n^2) 的解题思路，在 Leetcode 上可以AC。

思路1： 所有的回文串都是对称的。长度为奇数回文串以最中间字符的位置为对称轴左右对称，而长度为偶数的回文串的对称轴在中间两个字符之间的空隙。我们知道整个字符串中的所有字符，以及字符间的空隙，都可能是某个回文子串的对称轴位置。可以遍历这些位置，在每个位置上同时向左和向右扩展，直到左右两边的字符不同，或者达到边界。对于一个长度为n的字符串，这样的位置一共有n+n-1=2n-1个，在每个位置上平均大约要进行n/4次字符比较，于是此算法的时间复杂度是O(n^2)，空间复杂度 O(1)。

思路2： 动规 dp[i][j]。我们知道，像最长公共子串、最长公共子序列，以及最长回文子串、最长回文子序列等问题都可以采用动态规划的思路解决。在字符串 s 中，dp[i][j] 表示 s[i...j] 子序列的最优解。

设状态 f(i,j) 表示区间 s[i...j] 是否为回文串，则状态转移方程为

           |  true                              i=j
 f(i,j) =  |  s[i]=s[j]                         j=i+1
           |  s[i]=s[j] and f(i+1,j-1)          j>i+1

只需要开辟一个二维 bool 空间，记录子序列最优解即可。时间复杂度 O(n^2)，空间复杂度 O(n^2)。

Python 实现（思路1）：

class Solution:
    # AC版本：时间复杂度：O(n^2)， 空间复杂度：O(1)
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        lens = len(s)
        if lens <= 0:
            return s
        substr, maxLen = '', 0
        i = 1
        while i <= 2 * lens - 1: # 一共有 2*(lens-1) 个判断回文的位置
            j = i // 2
            k = 1
            if i % 2:  # 是字符
                while j - k >= 0 and j + k < lens:
                    if s[j-k] == s[j+k]:
                        k += 1
                    else:
                        break
                # k 为失配的间距
                sublen = (k - 1) * 2 + 1 # 子回文串的长度
                if  sublen > maxLen:
                    maxLen = sublen
                    substr = s[j-k+1:j+k] # 更新最大回文子串
            else:  # 是间隙
                while j - k >= 0 and j + k - 1< lens:
                    if s[j-k] == s[j+k-1]:
                        k += 1
                    else:
                        break
                # k 为失配的间距
                sublen = (k - 1) * 2 # 子回文串的长度
                if  sublen > maxLen:
                    maxLen = sublen
                    substr = s[j-k+1:j+k-1] # 更新最大回文子串 
            i += 1
        return substr

a = 'babad'
b = 'abbd'
c = 'eabcbaabcd'
d = 'aba'
e = 'abba'
print(Solution().longestPalindrome(a))  # 'bab'
print(Solution().longestPalindrome(b))  # 'bb'
print(Solution().longestPalindrome(c))  # 'cbaabc'
print(Solution().longestPalindrome(d))  # 'aba'
print(Solution().longestPalindrome(e))  # 'abba'

Java 实现（思路2）：

public Solution {
    public static String a(String s) {  
       int left=0, right=0;  // 回文串区间的上、下标
       int maxLen=1;  // 回文串之间的长度
       // 初始化f(i,j)，记录 [i,j] 之间是否为回文串
       boolean[][] dp=new boolean[s.length()][s.length()];
       
       for (int k=0; k<s.length(); k++) {
           for (int i=0; i+k<s.length(); i++) {
               int j=i+k;
               // 一个字符肯定为true
               if (i==j) dp[i][j]=true;
               // 比较当前两个字符（如bb），如果相等，则该区间一定为true
               if (j==i+1 && s.charAt(i)==s.charAt(j)) 
                   dp[i][j]=true;
               // 比较当前两个字符（如b...b），如果相等，则该区间取决于dp[i+1][j-1]是否为true 
               if (j>i+1 && s.charAt(i)==s.charAt(j)) 
                   dp[i][j]=dp[i+1][j-1];
               // 更新最大子串的上、下标和长度
               if (dp[i][j] && maxLen<j-i+1) { 
                   maxLen=j-i+1;
                   left=i;
                   right=j;
               }
           }
       }
       // substring返回上、下标之间的字符串（左闭右开，故right+1）
       return s.substring(left, right+1);    
    }
    
    public static void main(String[] args) {
        String s=new String("civiathmeaweherehighlyresol"); 
        System.out.println(a(s));  //hereh
    }
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018.03.18 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

python

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

python

登录后参与评论

0 条评论

热度