[数据结构与算法]LeetCode 热题 100 思路整理(C++) – Q5 最长回文子串

🔥LeetCode 热题 100 思路整理(C++) – Q5 最长回文子串
题目：给你一个字符串 s，找到 s 中最长的回文子串。
示例 1： //意思是只要找到一个就行了

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

示例 2： //意思是长度为2的只含相同字符的子串也算是回文子串

输入：s = “cbbd”
输出：“bb”

示例 3： //意思是长度为1的字符串是回文子串！临界条件

输入：s = “a”
输出：“a”

示例 4： //意思是单个字符也算是回文子串

输入：s = “ac”
输出：“a”

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring

解题：

• 由回文子串的案例可知，回文子串正读和反读是一样的，也就是从回文子串两端起，任意长度的新子串是完全相同的。

   如 bab、abba、abccba 等

• 另外，回文子串满足一个性质：回文子串的两端各增加一个相同的字符后，新的子串仍为回文子串。

   如 bab  -->  ababa  -->  cababac  -->  dcababacd

• 题目需要的返回数据是字符串，且是最长的，因此需要初始化两个变量存储结果

int maxlen = 1;
string palindrome;   
palindrome.push_back(s[0]);

• 考虑子串的数据结构，可以用二维bool数组存储所有子串的回文情况。

vector<vector<int>>  substr(n,vector<int>(n));
//初始化
for(int i = 0; i < n; i++)   substr[i][i] = true;

• 综上，可以考虑使用动态规划，从最简单的“长度为1的字符串是回文子串”开始，只要逐步判断两端字符是否相同即可！

if(s[i] != s[j]){
	substr[i][j] = false;
}else{
	if(j - i < 2) substr[i][j] =true;
	else substr[i][j] = substr[i+1][j-1];
}

• 最终代码

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        if(len<2) return s;

        int maxlen = 1;
        string palindrome;
        vector<vector<int>> substr(len,vector<int>(len));
        for(int i = 0; i < len; i++) substr[i][i] = true;
        palindrome.push_back(s[0]);

        for(int L = 2; L <= len; L++){
            for(int i = 0; i < len; i++){
                int j = L + i - 1;  //由起始位置和子串长度可得尾部位置
                if(j >= len) break;
                if(s[i] != s[j]) substr[i][j] = false;
                else{
                    if(j-i<2) substr[i][j] = true;
                    else substr[i][j] = substr[i+1][j-1];
                }

                if(substr[i][j] && maxlen < j-i+1){
                    maxlen = j - i + 1;
                    palindrome.clear();
                    for(int k = i; k <= j; k++) palindrome.push_back(s[k]);
                }
            }
        }
        return palindrome;
    }
};