C++ day57 回文子串 最长回文子串序列

题目1：647 回文子串

题目链接：回文子串

对题目的理解

返回字符串s中回文子串的个数，字符串s至少包含一个字符，且仅由小写字母组成。

动态规划

动规五部曲

1）dp数组及下标i的含义

dp[i][j]：[i,j]子串是否为回文子串，代表以s[i]为开头，s[j]为结尾的子串（左闭右闭）

2）递推公式

整体可以分为两种情况，s[i]==s[j]? ?s[i]!=s[j]

当s[i]等于s[j]时，有3种情况需要考虑：

j==i? 两元素重合，代表数组中只有1个元素，那么必是回文子串

j-i==1 两元素相邻，代表数组中有两个元素，且前提是两个元素相等，那么这也必是回文子串

j-i>1 两元素不相邻，但是首尾的两元素相等，仅仅在dp[i+1][j-1]是回文串的基础上，dp[i][j]才是回文串

s[i]!=s[j]时，当前子串一定不是回文串，dp[i][j]=false

3）dp数组初始化

根据dp数组的定义，将其进行初始化，初始化为false,

4）遍历顺序

根据递推公式，从下往上遍历，从左往右遍历

5）打印dp数组

代码

class Solution {
public:
    int countSubstrings(string s) {
        //定义并初始化dp数组
        vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));
        int result = 0;
        for(int i=s.size()-1;i>=0;i--){
            for(int j=i;j<=s.size()-1;j++){
                    if(s[i]==s[j]){
                        if(j-i<=1){
                            dp[i][j]=true;
                            result++;
                        }
                        else if(dp[i+1][j-1]==true){
                            dp[i][j]=true;
                            result++;
                        }
                    }
            }
        }
        return result;
    }
};

• 时间复杂度：O(n^2)
• 空间复杂度：O(n^2)

代码流程

法2：双指针法

首先确定回文串，就是找中心然后向两边扩散看是不是对称的就可以了。

在遍历中心点的时候，要注意中心点有两种情况：

1）一个元素可以作为中心点；

2）两个元素也可以作为中心点。

三个元素就可以由一个元素左右添加元素得到，四个元素则可以由两个元素左右添加元素得到，以此类推，因此，只分析一个元素作为中心点和两个元素作为中心点就可以了

代码

class Solution {
public:
    int extend(string& s,int i,int j,int n){
        int res;
        while(i>=0 && j<n && s[i]==s[j]){
            i--;
            j++;
            res++;
        }
        return res;
    }
    int countSubstrings(string s) {
        int result = 0;
        for(int i=0;i<s.size();i++){
            result += extend(s,i,i,s.size());
            result += extend(s,i,i+1,s.size());
        }
        return result;
    }
};

以上代码对于案例会计算错误，如图，原因就是未对res进行初始化

注意一定要对res进行初始化，不然会报以上错误，将代码修改为如下，就能够运行了

class Solution {
public:
    int extend(string& s,int i,int j,int n){
        int res=0;
        while(i>=0 && j<n && s[i]==s[j]){
            i--;
            j++;
            res++;
        }
        return res;
    }
    int countSubstrings(string s) {
        int result = 0;
        for(int i=0;i<s.size();i++){
            result += extend(s,i,i,s.size());
            result += extend(s,i,i+1,s.size());
        }
        return result;
    }
};

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

代码流程

题目2：516 最长回文子序列

题目链接：最长回文子序列

对题目的理解

返回字符串s中最长回文子序列的长度，字符串s至少包含一个字符，且仅由小写字母组成。

动态规划

动规五部曲

1）dp数组及下标i的含义

?dp[i][j]:[i,j]范围内的回文子序列的长度（左闭右闭）

2）递推公式

分为两种情况，s[i]==s[j]? ?s[i]!=s[j]

当s[i]==s[j]时，dp[i][j]=dp[i+1][j-1]+2，加2是因为s[i]与s[j]相等，在原来回文子序列长度dp[i+1][j-1]的基础上加上2（这两个元素相同）

当s[i]!=s[j]时，说明s[i]和s[j]的同时加入并不能增加[i,j]区间回文子序列的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列，因此要分为两种情况，考虑s[i]而不考虑s[j]? ?考虑s[j]而不考虑s[i]

1)考虑s[i]而不考虑s[j]? ?dp[i][j]=dp[i][j-1]

2)考虑s[j]而不考虑s[i-1]? dp[i][j]=dp[i+1][j]

dp[i][j]=max(dp[i][j-1],dp[i+1][j])

3）dp数组初始化

首先要考虑当i 和j 相同的情况，从递推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况，因为本题求的是最长回文子序列的长度，所以需要手动初始化一下，当i与j相同，那么dp[i][j]一定是等于1的，即：一个字符的回文子序列长度就是1。

根据递推公式，i一直加1，j一直减1，直到i==j

i==j时是初始化位置，指向了一个元素，一定是回文的，即dp[i][i]=1

！！！其他情况dp[i][j]初始为0就行，这样递推公式：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); 中dp[i][j]才不会被初始值覆盖，一定要初始化为0，这样才不会被覆盖

4）遍历顺序

根据递推公式，dp[i][j] 依赖于 dp[i + 1][j - 1] ，dp[i + 1][j] 和 dp[i][j - 1]，从下往上遍历，从左往右遍历，这两个for循环不可以颠倒，因为j依赖于i，因为字符串的范围是[i,j]，j一定是大于等于i的，一定是i在前，j在后。

5）打印dp数组

最终结果是dp[0][s.size()-1]? ?

代码

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        //定义dp数组
        vector<vector<int>> dp(s.size(),vector<int>(s.size(),0));
        //初始化dp数组
        for(int i=0;i<s.size();i++) dp[i][i]=1;
        for(int i=s.size()-1;i>=0;i--){
            for(int j=i+1;j<s.size();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][s.size()-1];
    }
};

• 时间复杂度: O(n^2)
• 空间复杂度: O(n^2)

代码流程