leetcode-5

5. 最长回文子串

1 题目描述

• 题目链接：5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例1：

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

示例2：

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

2 思路

  采用动态规划的方法来判断从某个下标到另一个下标间（包括左右端点）的字符串是否为回文串，如果是则判断当前子字符串的长度是否大于答案字符串的长度，若是则将答案字符串更新为当前的子字符串。

  动态数组dp[i][j]的意义是从下标i到j构成的字符串是否为回文串。很明显，当s[i]!=s[j]则dp[i][j]必定为false；而当s[i]==s[j]，可以分成三种情况：①i==j，此时子字符串为单个字符，必定为回文串，因而为true；②j - i == 1，此时子字符串包含两个字符，同样也为回文串，也为true；③j - i > 1，此时子字符串含有多个字符，要判断i~j是否为回文串，可以转换为i+1~j-1是否为回文串。

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.length();
        bool dp[len][len];
        memset(dp, 0, sizeof(dp));
        string res = "";
        for(int i = len - 1; i>= 0; --i){
            for(int j = i; j < len; ++j){
                if(s[i] != s[j]){
                    continue;
                }else{
                    if(j - i < 2){
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i+1][j-1];
                    }
                    if(dp[i][j] && j - i + 1 > res.length()){
                        res = s.substr(i, j-i+1);
                    }
                }
            }
        }
        return res;
    }
};