leetCode 5. 最长回文子串 动态规划 + 优化空间 / 中心扩展法 + 双指针

5. 最长回文子串 - 力扣（LeetC5. 最长回文子串 - 力扣（LeetCode）5. 最长回文子串 - 力扣（LeetC

给你一个字符串 s，找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

---

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

---

一、「中心扩展法 + 双指针​​​​​​​」

我的往期文章有详细介绍「​​​​​​​中心扩展法 + 双指针​​​​​​​」，大家感兴趣可以看一下：​​​​​​​leetCode 647.回文子串 动态规划 + 优化空间 / 中心扩展法 + 双指针-CSDN博客https://blog.csdn.net/weixin_41987016/article/details/133883091?spm=1001.2014.3001.5501

现在我们将用这个方法来解决本文中的此题：5. 最长回文子串 - 力扣（LeetCode）

class Solution {
public:
    vector<int> extend(string& s,int i,int j,int n) {
        while(i>=0 && j
            i--;
            j++;
        }
        return {i+1,j-1};
    }
    // 返回以 i, j 为中心的最长回文子串的左右边界
    string longestPalindrome(string s) {
        int n = s.size();
        vector<int> res{0,0};
        for(int i=0;i
            vector<int> sub1 = extend(s,i,i,n);
            vector<int> sub2 = extend(s,i,i+1,n);
            if (res[1] - res[0] < sub1[1] - sub1[0]) res = sub1;
            if (res[1] - res[0] < sub2[1] - sub2[0]) res = sub2;
        }
        return s.substr(res[0], res[1] + 1 - res[0]);
    }
};

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

---

 二、动态规划（详细可以看我的往期文章:leetCode 647.回文子串）

左边图是dp数组初始化，在填dp数组只会对右上三角进行数据更新，所以右边的图我就不画左下三角的0了。从图中，可得知有9个true，即有9个回文子串。还可以得知另一个信息，那就是回文子串有："a","b","d","d","b","a","dd","bddb","abddba"

注："dd"是回文子串的信息记录在(2,3)这个坐标，"bddb"是回文子串的信息记录在(1,4)这个坐标,"abddba"是回文子串的信息记录在(0,5)这个坐标，若为true，则该子串为回文。

(2,3),(1,4),(0,5)在左对角线上，所以观察的时候可以瞄准这条线上的坐标，分析信息

注：要明确和清晰dp[i][j] 表示区间范围[i,j]的子串是否为回文子串

这样就可以知道一个回文子串的起始和末尾，将其返回， 然后选取出最长回文子串

1.动态规划 二维dp 

class Solution {
public:
    // 动态规划 二维dp 
    string longestPalindrome(string s) {
        vectorbool>> dp(s.size(),vector<bool>(s.size(),false));
        vector<int> res{0,0};
        for(int i=s.size()-1;i>=0;i--) {
            for(int j=i;j < s.size();j++) {
                if(s[i] == s[j] && (j-i<=1 || dp[i+1][j-1])) {
                    dp[i][j] = true;
                    if (res[1] - res[0] < j - i) res = {i,j};
                }
            }
        }
        return s.substr(res[0], res[1] + 1 - res[0]);
    }
};

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

2.动态规划 二维dp + 优化空间

class Solution {
public: 
    // 动态规划 二维dp 优化空间
    string longestPalindrome(string s) {
        vectorbool>> dp(2,vector<bool>(s.size(),false));
        vector<int> res{0,0};
        for(int i=s.size()-1;i>=0;i--) {
            for(int j=i;j < s.size();j++) {
                if(s[i] == s[j] && (j-i<=1 || dp[(i+1)%2][j-1])) {
                    dp[i%2][j] = true;
                    if (res[1] - res[0] < j - i) res = {i,j};
                }else {
                    dp[i%2][j] = false;
                }
            }
        }
        return s.substr(res[0], res[1] + 1 - res[0]);
    }
};

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

 3.动态规划 一维dp + 优化空间

class Solution {
public:  
    // 动态规划 一维dp 
    string longestPalindrome(string s) {
        vector<bool> dp(s.size(),false);
        vector<int> res{0,0};
        for(int i=s.size()-1;i>=0;i--) {
            bool pre = false;
            for(int j=i;j < s.size();j++) {
                bool tmp = dp[j];
                if(s[i] == s[j] && (j-i<=1 || pre)) {
                    dp[j] = true;
                    if (res[1] - res[0] < j - i) res = {i,j};
                }else {
                    dp[j] = false;
                }
                pre = tmp;
            }
        }
        return s.substr(res[0], res[1] + 1 - res[0]);
    }
};

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

参考和推荐文章：

647. 回文子串 - 力扣（LeetCode）https://leetcode.cn/problems/palindromic-substrings/solutions/1530868/by-lfool-2mvg/