一、题目描述

二、解题思路

  • 首先，定义一个二维dp[len][len]布尔数组
  • dp[i][j]的值代表从s[i]到s[j]的这个子串是否为回文串
  • 状态转移方程：dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j];
  • 解释：如果一个串是回文串，那么掐头去尾，剩下的也是回文串，同时头尾元素一定相同，只有这样才会是回文串

三、解题代码

class Solution {
   
public:
    string longestPalindrome(string s) {
   
        string sln;
        int len = s.size();
        if (!len)
            return sln;
        if (len == 1)
            return s;
        int MAX = 1;
        int rear = 0, prior = 0;
        bool dp[len][len];
        for (int i = 0; i < len; i++)
            dp[i][i] = true;
        for (int i = 1; i < len; i++) {
   
            for (int j = 0; j < len; j++) {
   
                if (i + j < len) {
   
                    if (i == 1)
                        dp[j][i + j] = (s[j] == s[i + j]);
                    else
                        dp[j][i + j] = (dp[j + 1][i + j - 1]) && (s[j] == s[i + j]);
                    if (dp[j][i + j]) 
                        if (i + 1 > MAX) {
   
                            MAX = i + 1;
                            rear = j;
                            prior = i + j;
                        }
                }
            }
        }
        sln = s.substr(rear, prior - rear + 1);
        return sln;
    }
};

四、运行结果