力扣5. 最长回文子串

2023-12-16 04:49:01

动态规划

  • 思路:
    • 假设 dp[i][j] 为字符串 (i, j) 子串是否为回文的结果;
    • 那么 dp[i][j] = dp[i + 1][j - 1] 且 (s[i] == s[j]);
    • 长度为1的字符串都是回文;
      • 原字符串长度为1,是回文;
      • 原字符串子串长度为1,即 i = j,dp[i][i] = true;
    • 使用 begin 变量记录最长时的子串左边界,maxLen 缓存最长回文串的长度;
    • 遍历迭代计算出所有?dp[i][j] 的值:
      • 迭代子串长度 len,同时从左边界遍历;
class Solution {
public:
    string longestPalindrome(string s) {
        int size = s.size();
        if (size < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;

        std::vector<std::vector<bool>> dp(size, std::vector<bool>(size));

        // len 1
        for (int i = 0; i < size; ++i) {
            dp[i][i] = true;
        }

        for (int len = 2; len <= size; ++len) {
            for (int left = 0; left < size; ++left) {
                int right = len + left - 1;
                if (right >= size) {
                    break;
                }

                if (s[left] != s[right]) {
                    dp[left][right] = false;
                } else {
                    if (right - left < 3) {
                        dp[left][right] = true;
                    } else {
                        dp[left][right] = dp[left + 1][right - 1];
                    }
                }

                if (dp[left][right] && (right - left + 1 > maxLen)) {
                    maxLen = right - left + 1;
                    begin = left;
                }
            }
        }

        return s.substr(begin, maxLen);
    }
};

文章来源:https://blog.csdn.net/N_BenBird/article/details/135026825
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。