5. 最长回文子串

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

示例 1：

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2：

输入: “cbbd”
输出: “bb”

解题思路
子串问题，动态规划
1.最优子问题
dp[i][j],表示第i个字符到第j个字符是否是回文字符串
若dp[i+1][j-1]是回文字符串且s[i]==s[j],则dp[i][j]也为回文字符串
2.难点:边界问题
当s为单个字符时
初始条件：当s为三个字符时，前后相等即为回文字符串
大于三个字符时，用传递公式dp[i][j]=dp[i+1][j-1];

class Solution:
    def longestPalindrome(self, s: str) -> str:
        #动态规划，找到最优子问题；
        #dp[i][j],确定j，遍历i看ij是否为回文字符串；
        size=len(s)
        dp=[[False for _ in range(size)] for i in range(size)] #初始化列表
        start=0
        Lens=0        #初始化为0，不然会跳过单个字符的情况，输出至少两个字符
        if size==1:   #长度为一，特殊情况
            return s

        for j in range(1,size):         
            dp[j][j]=True         #初始化，单个为true
            for i in range(j):               
                if j-i<3 and s[i]==s[j]:      #字符串长度小于等于3时，且相等
                    dp[i][j]=True                  #为true
                elif s[i]==s[j]:                  #长度若不小于3，递推公式
                    dp[i][j]=dp[i+1][j-1]       #右上递推
                if dp[i][j] and j-i+1>Lens:    #找最大值
                    start=i                     #找起点
                    Lens=j-i                      #长度为终点-起点
        return s[start:start+Lens+1]            #输出，右闭，要+1

C++
注意点
先遍历数组，把每个数组开头的单个初始化为1，即回文串；
每个字符开头的2个字符，若相等，初始化为1，即回文串；

以i结尾的子串，遍历每一个j，若j<i-1且s[j]==s[i]，则该dp[j][i]=1（ j 开头， i 结尾）；
若i和j隔了不只一个数且s[j]==s[i]，则dp[j][i]=dp[j+1][i-1]；

必须先初始化以i结尾的子串，再逐个遍历i之前的字符j
根据公式dp[i][j]=dp[i+1][j-1]；
开头的字符——从后往前推；
结尾的字符——从前往后推；
所以结尾循环在外，开头循环在内，先要得到dp[每一个开头][i-1]，才能得到，dp[j+1][i-1]；

class Solution {
    
public:
    string longestPalindrome(string s) {
    
        //dp[i][j]  //s[i]~s[j]为回文
        int len=s.size();
        if(len<=1) return s;
        vector<bool> tmp(s.size(),0);
        vector<vector<bool>> dp(s.size(),tmp);
        
        int M=0;
        int start=0; //初始化为0，不然单个数无法输出
        int end=0;
        for(int i=0;i<len;i++)
        {
    
            for(int j=i;j>=0;j--)
            {
    
                if(s[j]==s[i])
                {
    
                    if(i<=j+2)
                        dp[j][i]=1;
                    else dp[j][i]=dp[j+1][i-1];
                }
                if(dp[j][i]&& M<i-j)
                    {
    
                        M=i-j;
                        start=j;
                        end=i;
                    }
            }
        }
        return s.substr(start,end-start+1);
    }
};

动态规划要注意递推方向

解法2:中心拓展法
每个点可以作为一个中心拓展；
每两个点的中间可作为一个中心拓展；
对每个可拓展点进行拓展，返回拓展后的回文子串长度；

拓展函数

int Expendfromcenter(string &s, int left,int right)
    {
    
        int n=s.size();
        while(left>=0&&right<n&&s[left]==s[right])
        {
    
            --left;
            ++right;
        }
        return right-left-1;//返回长度   需要-2
    }

主函数

string longestPalindrome(string s) {
    
        int len=s.size();
        int maxlen=0;
        int start=0;
        int wide=0;
        int tmp1;
        int tmp2;
        for(int i=0;i<len;i++)
        {
    
            tmp1=Expendfromcenter(s,i,i);
            tmp2=Expendfromcenter(s,i,i+1);
            if(tmp1>maxlen)
            {
       
                maxlen=tmp1;
                start=i-tmp1/2;
                wide=tmp1;
            }
            if(tmp2>maxlen)
            {
    
                maxlen=tmp2;
                start=i-(tmp2/2)+1;
                wide=tmp2;
            }
        }
        
        return s.substr(start,wide);
    }

完整代码

class Solution {
    
public:
    string longestPalindrome(string s) {
    
        int len=s.size();
        int maxlen=0;
        int start=0;
        int wide=0;
        int tmp1;
        int tmp2;
        for(int i=0;i<len;i++)
        {
    
            tmp1=Expendfromcenter(s,i,i);
            tmp2=Expendfromcenter(s,i,i+1);
            if(tmp1>maxlen)
            {
       
                maxlen=tmp1;
                start=i-tmp1/2;
                wide=tmp1;
            }
            if(tmp2>maxlen)
            {
    
                maxlen=tmp2;
                start=i-(tmp2/2)+1;
                wide=tmp2;
            }
        }
        
        return s.substr(start,wide);
    }

private:
    int Expendfromcenter(string &s, int left,int right)
    {
    
        int n=s.size();
        while(left>=0&&right<n&&s[left]==s[right])
        {
    
            --left;
            ++right;
        }
        return right-left-1;//返回长度   需要-2
    }
};

516. 最长回文子序列

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

示例 1:

输入:

"bbbab"
输出:

4

一个可能的最长回文子序列为 “bbbb”。

示例 2:

输入:

"cbbd"
输出:

2

一个可能的最长回文子序列为 “bb”。

回文子序列
回文子序列可以不连续，回文子串一定连续；

解法：动态规划
dp【i】【j】表示从i开始到j结束的子串里回文子序列的大小；

（1）初始化：dp【i】【i】为1；
（2）递推：从左往右推，从下往上推（坐下——>右上）；
当s【i】==s【j】时，dp【i】【j】=dp【i+1】【j-1】+2；
当s【i】！=s【j】时，dp【i】【j】=max（dp【i+1】【j】，dp【i】【j-1】；
（3）得到结果为dp【0】【n-1】；

class Solution {
    
public:
    int longestPalindromeSubseq(string s) {
    
        //最长回文子序列——可以不连续
        int n=s.length();
        vector<int> tmp(n,0);
        vector<vector<int>> dp(n,tmp);
        for(int j=0;j<n;j++) dp[j][j]=1;

        for(int i=n-2;i>=0;i--)
            for(int j=i+1;j<n;j++)
            {
    
                if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2;
                else dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
            }
        return dp[0][n-1];
    }
};

对’bbbab‘得到的dp如下：

1 2 3 3 4 
0 1 2 2 3 
0 0 1 1 3 
0 0 0 1 1 
0 0 0 0 1 

647. 回文子串

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

示例 1:

输入: "abc"
输出: 3
解释: 三个回文子串: "a", "b", "c".

示例 2:

输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".

注意:

输入的字符串长度不会超过1000。

动态规划
对每两个ij判断是否为回文串，是则总数+1；

class Solution {
    
public:
    int countSubstrings(string s) {
    
        int n=s.size();
        vector<vector<int>> dp(n,vector<int>(n,0));
        //判断ij是不是回文
        int cnt=0;
        for(int i=n-1;i>=0;i--){
    
            dp[i][i]=1;
            ++cnt;
            for(int j=i+1;j<n;j++)
            {
    
                if(s[j]==s[i])
                {
    
                    if(j<i+2) dp[i][j]=1;
                    else dp[i][j]=dp[i+1][j-1];
                    if(dp[i][j]) ++cnt;
                }
            }
        }
        return cnt;
        }
};

若要dp i和j 之间的回文串数量，不满足最优子问题，如下，无法统计正确答案；

class Solution {
    
public:
    int countSubstrings(string s) {
    
        int n=s.size();
        vector<vector<int>> dp(n,vector<int> (n,0));
        //单个字符为一个,初始化为1
        //s[i]==s[j] dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]+1;
        //s[i]!=s[j] dp[i][j]=max(dp[i+1][j],dp[i][j-1])+1;
        for(int i=n-1;i>=0;i--){
    
            dp[i][i]=1;
            for(int j=i+1;j<n;j++)
            if(s[i]==s[j])
                dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]+1/;
            else 
                dp[i][j]=max(dp[i+1][j],dp[i][j-1])+1;
        }
        for(int i=0;i<n;i++){
    
            for(int j=0;j<n;j++)
                cout<<dp[i][j]<<" ";
                cout<<endl;
            }
        return dp[0][n-1];
    }
};

s[i]==s[j]时无法判断该子串整体是否为回文子串。

中心拓展法

对每个字符和两个字符中的点进行左右拓展，能拓展几次说明有几个回文字符串；

class Solution {
    
public:
    int countSubstrings(string s) {
    
        int n=s.size();
        int left;
        int right;
        int res=0;
        for(int i=0;i<2*n-1;i++)
        {
    
            left=i/2;
            right=left+i%2;
            while(left>=0&&right<n&&s[left]==s[right])
            {
    
                --left;++right;
                ++res;
            }
        }
        return res;
        }
};