leetcode5：最长回文子串

链接

leetcode

题目描述

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

C++ 代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;

/*
    双指针

    枚举回文串的中心 i，然后分两种情况向两边扩展，直到遇到不同字符为止:
        1.若回文串长度为奇数，则依次判断 s[i−k] == s[i+k], k = 1, 2, 3, ...
        2.若回文串长度为偶数，则依次判断 s[i−k] == s[i+k−1], k = 1, 2, 3, ...
    遇到不同字符时，就找到了以 i 为中心的回文串边界。

    时间复杂度：O(n^2)
        其中 n 是字符串的长度。
        由于字符串长度小于 1000，所以可以枚举所有可能的情况。
    空间复杂度：O(1)
*/
class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) {
            return "";
        }

        string res;
        for (int i = 0; i < s.size(); i++) {
            // 长度为奇数，以 s[i] 为中心的最长回文子串
            string s1 = check(s, i, i);
            // 长度为偶数，以 s[i] 和 s[i+1] 为中心的最长回文子串
            string s2 = check(s, i, i + 1);
            res = res.size() > s1.size() ? res : s1;
            res = res.size() > s2.size() ? res : s2;
        }
        return res;
    }
    
    string check(const string& s, int l, int r) {
        // 防止下标越界，向两侧扩展
        while (l >= 0 && r < s.size() && s[l] == s[r]) {
            l--, r++;
        }
        // 返回以 s[l] 和 s[r] 为中心的最长回文串
        return s.substr(l + 1, r - l - 1);
    }
};

/*
    状态表示：
        f[i][j] 表示 s[i...j] 是否为回文串
    状态计算：
        f[i][j] = s[i-1] == s[j-1] && (j-i < 2 || f[i+1][j-1])

    时间复杂度：O(n^2)
    空间复杂度：O(n^2)
*/
class Solution_2 {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<int>> f(n+1, vector<int>(n+1, 0));
        int start = -1, length = 0;

        for (int i = n; i >= 1; i--) { // 倒序填充左边界 i
            for (int j = i; j <= n; j++) { // 右边界 j 从 i 开始向右扩展
                f[i][j] = s[i-1] == s[j-1] && (j - i < 2 || f[i+1][j-1]);
                
                if (f[i][j] != 0 && length < j - i + 1) {
                    start = i;
                    length = j - i + 1;
                }
            }
        }

        return s.substr(start - 1, length);
    }
};

int main() {
    vector<string> test_cases = { "babad", "cbbd" };

    for (auto s : test_cases) {
        Solution solution;
        cout << "Input: " << s << endl;
        string result = solution.longestPalindrome(s);
        cout << "Output: " << result << endl;
    }

    return 0;
}