【LeetCode热题100】【多维动态规划】最长回文子串

叶茂林

发布于 2024-04-24 08:16:03

780

发布于 2024-04-24 08:16:03

文章被收录于专栏：叶子的开发者社区叶子的开发者社区

题目链接：5. 最长回文子串 - 力扣（LeetCode）

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

如果暴力的话，两层循环找出所有子串，一层循环判断回文，这样重复判断了回文，存在这样的一个事实：如果s[i,j]是回文字符串，那么s[i+1,j-1]也是回文字符串

用一个二维布尔数组dp，dp[i][j]表示字符串s[i,j]是不是回文字符串，取决于s[i]是否等于s[j]并且dp[i+1][j-1]为真或者i和j之间没有或者只有一个字符

二维动态规划数组，由于dp[i][j]需要dp[i+1][j-1]，所以需要从左下角开始往右上角遍历

class Solution {
public:
    string longestPalindrome(string s) {
        string ans = "";
        int n = s.size();
        vector<vector<bool> > dp(n, vector<bool>(n));
        for (int i = n - 1; i >= 0; --i)
            for (int j = i; j < n; ++j)
                if (s[i] == s[j] && (j - i <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    if (ans.size() < j - i + 1)
                        ans = s.substr(i, j - i + 1);
                }
        return ans;
    }
};

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-04-23，如有侵权请联系 cloudcommunity@tencent.com 删除

字符串