LeetCode 第5题 Longest Palindromic Substring 最长回文子串

  这道题实在是很经典了，解法也很多，我只写出了暴力解法-_-||，功力不够啊，把这些解法都学会总结一下，看看是怎么一步一步优化过来的。

• 题目描述
• 题目解法
  • 暴力解法
  • 动态规划解法
  • 从中间开始向两边扩展的办法
  • Manacher’s 算法

题目描述

  给定一个子串，找出其中最长的回文子串，注意子串一定要是连续的。

题目解法

暴力解法

  我的暴力解法思路很简单，从大到小枚举可能的长度$(len,1)$，然后对每个长度枚举起点，然后判断枚举是否为回文串，如果是则终止枚举然后输出。时间复杂度为$O(n^3)$,最低效的做法，并没用上上一个计算出来的回文串结果。

class Solution {
public:
    string longestPalindrome(string s) {
        //字符串长度
        int len = s.size();
        
        string ans;
        for(int max_len = len;max_len>=1;max_len--)
        {   
	        for(int start=0;start+max_len<=len;start++)
	            {
	                string substr = s.substr(start,max_len);
	                if(judge(substr)) {return substr;} 
	            }
        }
        
        return s;
    }
    
    bool judge(string s)
    {
        int len = s.size();
        
        for(int i=0,j=len-1;i<j;i++,j--)
            if(s[i]!=s[j]) return false;
        
        return true;
    }
};

动态规划解法

  暴力解法中，我们可以避免大量的重复判断一个串是否为回文串的不必要计算，动态规划的思想为定义一个数组：

$$dp[i][j],表示从i开始到j结束的子串是否为回文串$$

这样我们可以得到如下的递推式：

$$dp[i][j]=dp[i+1][j-1]\&\&s[i]==s[j]$$

动态规划还需要一个初始条件，不难想到为：

$$dp[i][i]=true$$ $$dp[i][i+1]=s[i]==s[i+1]$$

这样我们就可以通过长度为1的结果，长度为2的结果，从而推出长度为3,4,5…..的结果，动态规划时间复杂度为$O(n^2)$，空间复杂度为$O(n^2)$

class Solution {
public:
    string longestPalindrome(string s) {
      int n = s.length();
  int longestBegin = 0;
  int maxLen = 1;
  bool table[1000][1000] = {false};
  for (int i = 0; i < n; i++) {
    table[i][i] = true;
  }
  for (int i = 0; i < n-1; i++) {
    if (s[i] == s[i+1]) {
      table[i][i+1] = true;
      longestBegin = i;
      maxLen = 2;
    }
  }
  for (int len = 3; len <= n; len++) {
    for (int i = 0; i < n-len+1; i++) {
      int j = i+len-1;
      if (s[i] == s[j] && table[i+1][j-1]) {
        table[i][j] = true;
        longestBegin = i;
        maxLen = len;
      }
    }
  }
  return s.substr(longestBegin, maxLen);
    }
};

从中间开始向两边扩展的办法

  我们可以通过进一步优化，使得时间复杂度为$O(n^2)$、空间复杂度为$O(1)$，回文串都是从中间向两边对称扩展的，所以我们可以枚举回文子串中间的位置，一共有$2N-1$种情况，为什么不是$N$呢？注意到，当一个回文串长度为偶数时，其实我们是从两个字符的中间开始枚举的。注意这里处理枚举情况的技巧.

class Solution {
public:
    string expanding_longeststring(string s,int c1,int c2)
    {
        int l = c1,r = c2;
        int len = s.size();
        for(;l>=0&&r<len&&s[l]==s[r];l--,r++);
        
        return s.substr(l+1,r-l-1); 
    }
    
    string longestPalindrome(string s) {
        
        int len = s.size();
        if(len==0) return s;
        string ans;
        ans = s.substr(0,1);
        
        string temp;
        for(int i = 0;i<len;i++)
        {
            temp = expanding_longeststring(s,i,i);
            
            if(temp.size()>ans.size())
            {
                ans = temp;
            }
            
            temp = expanding_longeststring(s,i,i+1);
            
            if(temp.size()>ans.size())
            {
                ans = temp;
            }
        }
        
        return ans;
    }
};

Manacher’s 算法

  马拉车算法，(⊙o⊙)…，额这个名字挺不错的，这么炫酷的算法不学会简直对不起自己，这个算法的时间复杂度为$O(n)$、空间复杂度为$O(n)$。下面总结一下这个算法。
  该算法将原来的字符串进行扩展，将两边和每个字符的中间插入‘#’，例如S = “abaaba”, T = “#a#b#a#a#b#a#”。
  然后算法采用了一个数组$P$，来保存当前位置回文串的最大长度，即$P[i]$保存$T$中以第$i$个位置为中心的向左或向右最大能扩展的回文子串长度。也就是$T_{i-P[i]}…..T_{i+P[i]}$为回文子串，例如下面的结果。不难发现，$P[i]$即为原字符串中以$i$为中心的最长回文子串长度。

  不难看出，$P$数组具有很强的对称性，那我们能否通过前面计算的$P[i]$从而快速得到后面的$P[i]$呢？答案是可以，算法通过维护两个中间变量$C、R$来快速计算各个$P[i]$，其中$C$代表当前最长回文子串的中心点，$R$表示该子串的右边界，其实有$R=C+P[i]$，下面来分析一下各种情况：

  上图中假设我们已经计算出来了$P[0]$到$P[11]$,当前$C=11,R=20,P[C]=9$，假设此时$i=13$，也就是现在我们要计算$P[13]$的值，其中$i=13$关于$C$的对称点为$i’=9$，通过对称性，像上图绿线所示，显然有$P[i]=P[i’]$，所以我们通过这种对称性就可以快速得到$P[i]$的值。那么是否所有的情况都满足这种性质呢？并不是，下面我们来看另外一种情况：

  假设我们现在要计算$i=15$的值，那么根据上面的分析，是不是有$P[15]=P[7]=7$呢？显然，并不是。原因是，我们看到由于$P[i’]=7$红色线部分已经超出了我们当前最长回文子串的左边界，同理我们的$P[i]$的对应部分也超出了右边部分，所以超出的部分并不满足对称性，我们不能计算。现在我们知道了，$i$至少能扩展到右边界$R$，也就是$P[i]\geq 5$，剩下还能扩展多少就需要我们自己判断了，$P[21]!=P[9]$,所以有$P[i]=5$。

  总结一下，分以下情况：

• $i<R$
  • $R-i\leq P[i]$，这种情况下我们的对称区域不会超过右边界，所以我们直接令$P[i]=P[i’]$，其中$i’$为$i$关于$C$的对称点
  • $R-i >P[i]$，这种情况下我们的对称区域超过了右边界，只知道$P[i]\geq R-i$，还能扩展多少需要我们自己接下来进行判断
• $i\geq R$
  • 这种情况下超出了我们的先验知识，我们只能令$P[i]=0$，然后自己接下来一步步判断最大能伸展多少

这一步判断关键代码如下：

i_mirror = 2*C-i;
P[i] = (R>i)?min(R-i,P[i_mirror]):0;

  现在最后一步就是我们怎么更新$C、R$，很简单，当我们计算$i$位置时，发现将$R$进行了扩展，那我们就让$C=i,R=i+P[i]$。最后我们只需要扫描一遍$P$数组，找出其中索引和最大值就OK了。
  扩展$R$最多需要$N$次，而枚举和测试每个中心$C$，也最多需要$N$次。所以算法一共需要$2N$步，时间复杂度为$O(N)$

class Solution {
public:
   string preprocessing(string s)
   {
       int len = s.size();
       string str;
       if(len==0) str = "$^";
       else str="$";
       
       for(int i=0;i<len;i++)
           str+='#'+s.substr(i,1);
       
       str+="#^";
       
       return str;
   }
    
    string longestPalindrome(string s) {
        
        string str = preprocessing(s);
        int len = str.size();
        int C=0,R =0;
        //申请保存中间变量的数组
        int *P = new int[len+10];
        
        for(int i=1;i<len;i++)
        {
            int mirror_i = 2*C - i;
            //要在边界区域内
            P[i] = (R>i)?min(P[mirror_i],(R-i)):0;
            
            //下面继续扩充P[i]
            while(str[i-P[i]-1]==str[i+P[i]+1]) P[i]++;
            
            //下面更新C，R
            if(i+P[i]>R)
            {
                C=i;
                R = i+P[i];
            }
            
        }
        
        int max_length = 0;
        int idx = 0;
        //寻找最大值
        for(int i=1;i<len;i++)
        {
            if(P[i]>max_length)
            {
                max_length = P[i];
                idx = i;
            }
        }
        delete P;
        return s.substr((idx-max_length)/2,max_length);
    }
};