炒一下冷饭---回文子串问题

好久没刷题了，为了准备秋招，面了几家公司提前感受面试氛围，一直在背八股文~

后面不打算再面了，还是要回归基础~

今天炒个冷饭，看一下回文子串的问题，奇怪的是leetcode这个题我竟然没有写过 0 . 0

题目短的可怜，证明它真的简单的很多人不屑去做。。

思路：

一、中心扩展法，直接上代码，没有什么好解释的 

class Solution {
public:
    string longestPalindrome(string s) {
        int n=s.size();string s1,s2;
        int result=INT_MIN;
        if(n==0||n==1)return s;
        for(int index=0;index<n;index++)
        {
            int left=index;
            int right=index;
            int num1=1;
            while(left>=0&&right<n){
                if(s[left]==s[right])
                {
                    if(left!=right)num1+=2;
                    if(num1>=s1.size())s1=s.substr(left,num1);
                }
                else break;
                left--;
                right++; 
            }
        }
        for(int index=0;index<n;index++)
        {
            int indey=index+1;
            int index_1=index;
            int index_2=indey;
            int num2=0;
            while(index_1>=0&&index_2<n&&s[index_1]==s[index_2]){
                num2+=2;
                if(num2>=s2.size())s2=s.substr(index_1,num2);
                index_1--;index_2++;
            }
        }
        return s1.size()>s2.size()?s1:s2;
    }
};

二、动态规划

动规适合解决无数重复的子问题，它的思想其实就是递归。

回文串的重复子问题是什么呢？

        如果一个字符串 s 是 回文串，那么 它去掉首尾肯定也是回文串【s.size()>2】,如下所示：

 所以，重复子问题，就是去判断 子串是否是回文串。

动规五部曲：

1.dp[i][j]含义：表示 s 下标 从 i  到  j  是否为回文串；

2.初始化：每一个字符都是一个回文子串

3.递推公式：考虑边界条件：如果字符串长度为 2、3，只要保证 s[i]==s[j]就可判断 它是回文

4.遍历：从前往后

5.打印dp

代码：

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size()==1)return s;
        int begin=0;
        int maxlen=1;
        vector<vector<int>>dp(s.size(),vector<int>(s.size()));
        //dp 表示 s 从 i  到  j  是否为回文子串；
        for(int i=0;i<s.size();i++)dp[i][i]=1;//初始化，本身肯定是回文串
        for(int length=2;length<=s.size();length++)
        {
            for(int leftindex=0;leftindex<s.size();leftindex++)
            {
                int rightindex=length+leftindex-1;
                if(rightindex>=s.size())break;//如果右边界越界了就跳出
                //如果 左右边界值不等 显然不能为回文串
                if(s[leftindex]!=s[rightindex])dp[leftindex][rightindex]=0;
                else{// 奇数 AbA保证左右相等就行 偶数 AA 保证 左右相等就行
                    if(rightindex-leftindex<=2)dp[leftindex][rightindex]=1;
                    else{//如果字符串长度>3，递归判断前面一个子串是否是回文串
                        dp[leftindex][rightindex]=dp[leftindex+1][rightindex-1];
                    }
                }
                //找到了一个回文串就更新一次 begin 与 maxlen
                if(dp[leftindex][rightindex]&&rightindex-leftindex+1>maxlen){
                    maxlen=rightindex-leftindex+1;
                    begin=leftindex;
                }
            }
        }
        return s.substr(begin,maxlen);
    }
};

 遍历不太符合正常的动规方法，个人感觉不如 中心扩展法来的实在，毕竟空间复杂度都是O(n^2)