最长回文子串

005_find_longest_palindrome

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

输入: “babad”

输出: “bab”

注意: “aba” 也是一个有效答案。

1.反序最长公共字串&

最长公共子串是我们一个比较熟悉的问题,所以我想尽量往上靠

很明显,回文串正读反读都是一样的,所以(是回文串)->(反序是公共字串),而倒过来不一定成立,所以(反序是公共字串)的子串集合包含了(回文串)子串集,那我们就找前者中最长的,再判断是否是回文串,不是就再找下一个最长的,直至找到

既然用到了,就就先把最长公共子串,最长公共子序列写一遍

  • 最长公共子串(The Longest Common Substring) 两个字符串张成一个二维区域,区域中每个点记录对应的两个字符的匹配状况(1 or 0),然后寻找最大的对角线为1(都匹配上了)的子区域,既是最大公共字串
def find_lcsubstr(s1, s2):
	matrix=[[0 for i in range(len(s2)+1)]  for j in range(len(s1)+1)]
	max=0
	p=0
	for i in range(len(s1)):
		for j in range(len(s2)):
			if s1[i]==s2[j]:
				matrix[i+1][j+1]=matrix[i][j]+1
				if matrix[i+1][j+1]>max:
					max=matrix[i+1][j+1]
					p=i+1
	return s1[p-max:p],max

  • 最长公共子序列 (The Longest Common Subsequence) 我专门写了一篇Blog来分析最长公共子序列的动态规划算法
def find_lcseque(s1, s2):
  matrix=[[0 for i in range(len(s2)+1)]  for j in range(len(s1)+1)]
  for p1 in range(len(s1)):
    for p2 in range(len(s2)):
      if s1[p1] == s2[p2]:
        matrix[p1+1][p2+1] = matrix[p1][p2]+1
      else:
        matrix[p1+1][p2+1] =max(matrix[p1][p2+1],matrix[p1+1][p2])
  return matrix[-1][-1]

然后就是这道题的代码了.不得不提的是,虽然我预感到了这个算法会表现很差,但没想到会那么差…

事后冷静分析了一波,大量时间消耗在了记录最长公共子串的时候,毕竟是O(n^2)的时间复杂度,而构建一个最长公共子串备忘录时间消耗比寻找最长子串多一些,导致这段代码很垃圾

class Solution:
  def longestPalindrome(self, s: 'str') -> 'str':
    matrix=[[0 for i in range(len(s)+1)]  for j in range(len(s)+1)]
    dic = {}
    s1=s[::-1]
    if s=="":return ""
    if s==s1:return s
    for i in range(len(s)):
      for j in range(len(s)):
        if s[i]==s1[j]:
          matrix[i+1][j+1]=matrix[i][j]+1
          if matrix[i+1][j+1] in dic.keys():
            dic[matrix[i+1][j+1]].append((i+1-matrix[i+1][j+1],i+1))
          else:
            dic[matrix[i+1][j+1]] = [(i+1-matrix[i+1][j+1],i+1)]

    while True:        
      for index in dic.pop(max(dic.keys())): #检验最长子序列是否回文
        if s[index[0]:index[1]] == s[index[0]:index[1]][::-1]:
          return s[index[0]:index[1]]
        else:
          pass    

执行用时: 10148 ms, 在Longest Palindromic Substring的Python3提交中击败了2.15% 的用户

内存消耗: 142.4 MB, 在Longest Palindromic Substring的Python3提交中击败了10.66% 的用户


2.暴力

心态崩了的我去看官方题解,发现还是一如既往的有暴力法

要是暴力法(O(n^3))都比第一种方法表现好,我就只有默念大力出奇迹了

幸好,copy了一个暴力破解的代码,发现时间超标通不过,稍微有点安慰

# copy自https://blog.csdn.net/asd136912/article/details/78987624
class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        l = len(s)
        max_length = 0
        palindromic = ''
        if len(s) == 1:
            return s
        for i in range(l):
            for j in range(i + 1, l):
                is_palindromic = True
                for k in range(i, int((i + j) / 2) + 1):
                    if s[k] != s[j - k + i]:
                        is_palindromic = False
                        break
                if is_palindromic and (j - i + 1) > max_length:
                    max_length = j - i + 1
                    palindromic = s[i:j + 1]
        if palindromic == '':
            palindromic = s[0]
        return palindromic

通不过


3.Manacher~

看这个算法拥有专门的命名,就感觉算法不会很简单 我看的这篇文章,讲的很清楚

文章里附的是c++,返回值是长度,需要稍微调整一下

// copy from https://subetter.com/algorithm/manacher-algorithm.html
#include <iostream>  
#include <cstring>
#include <algorithm>  

using namespace std;

char s[1000];
char s_new[2000];
int p[2000];

int Init()
{
    int len = strlen(s);
    s_new[0] = '$';
    s_new[1] = '#';
    int j = 2;

    for (int i = 0; i < len; i++)
    {
        s_new[j++] = s[i];
        s_new[j++] = '#';
    }

    s_new[j] = '\0';  // 别忘了哦

    return j;  // 返回 s_new 的长度
}

int Manacher()
{
    int len = Init();  // 取得新字符串长度并完成向 s_new 的转换
    int max_len = -1;  // 最长回文长度

    int id;
    int mx = 0;

    for (int i = 1; i < len; i++)
    {
        if (i < mx)
            p[i] = min(p[2 * id - i], mx - i);  // 需搞清楚上面那张图含义, mx 和 2*id-i 的含义
        else
            p[i] = 1;

        while (s_new[i - p[i]] == s_new[i + p[i]])  // 不需边界判断,因为左有'$',右有'\0'
            p[i]++;

        // 我们每走一步 i,都要和 mx 比较,我们希望 mx 尽可能的远,这样才能更有机会执行 if (i < mx)这句代码,从而提高效率
        if (mx < i + p[i])
        {
            id = i;
            mx = i + p[i];
        }

        max_len = max(max_len, p[i] - 1);
    }

    return max_len;
}

int main()
{
    while (printf("请输入字符串:\n"))
    {
        scanf("%s", s);
        printf("最长回文长度为 %d\n\n", Manacher());
    }
    return 0;
}

然后python重写一下:

(重写难度不大,但重写的时候,千万别去看c++代码,不同语言的计数习惯和一些小地方搅到一起直接爆炸,搅了很久我理清思路忘掉c++顺着算法重写的)

class Solution:
    def longestPalindrome(self, s):
        if s=="":return ""
        if s==s[::-1]:return s
        s = '#'+'#'.join(s)+'#'
        lens, max_len, mx = len(s), -1, 0
        p = [0] * lens
        result = ""

        for i in range(lens):
            if i < mx:
                p[i] = min(p[2 * id - i], mx - i)
            else:
                p[i] = 1
            while True:
                if i - p[i] < 0 or i + p[i] >= lens:
                    break
                if s[i - p[i]] == s[i + p[i]]:
                    p[i] += 1
                else:
                    break
            if mx < i + p[i]:
                id = i
                mx = i + p[i]
            if p[i] > max_len:
                max_len = p[i] - 1
                result = s[i - p[i] + 1: i + p[i]]
        return result.replace("#", "")

执行用时: 120 ms, 在Longest Palindromic Substring的Python3提交中击败了85.25% 的用户

内存消耗: 13.3 MB, 在Longest Palindromic Substring的Python3提交中击败了13.03% 的用户

4.扫地僧法

英文讨论区里有一个11行的代码,作者声称是由c++改写来的,但原c++代码已经不可见了,关于这段代码没有解释,我看了半天也没看懂

# copy from https://leetcode.com/problems/longest-palindromic-substring/discuss/3190/
def longestPalindrome(self, s):
    lenS = len(s)
    if lenS <= 1: return s
    minStart, maxLen, i = 0, 1, 0
    while i < lenS:
        if lenS - i <= maxLen / 2: break
        j, k = i, i
        while k < lenS - 1 and s[k] == s[k + 1]: k += 1
        i = k + 1
        while k < lenS - 1 and j and s[k + 1] == s[j - 1]:  k, j = k + 1, j - 1
        if k - j + 1 > maxLen: minStart, maxLen = j, k - j + 1
    return s[minStart: minStart + maxLen]
本文总字数: 4271