力扣 5. 最长回文子串

力扣题目链接

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

示例 1：
输入：s = "babad"
输出："bab"
解释："aba"同样是符合题意的答案

示例 2：
输入：s = "cbbd"
输出："bb"

动态规划，时间复杂度 O ( n 2 ) O(n^2) O(n2)，空间复杂度 O ( n ) O(n) O(n)：

动态规划五步：

1. 确定dp数组以及其下标的含义
2. 确定递推公式
3. 初始化dp数组
4. 确定遍历顺序
5. 举例推导dp数组

class Solution {
public:
    string longestPalindrome(string s) {
        vector> records(s.length(), vector(s.length(), false));
        int max_size = -1;
        int left_position;

        for (int left = s.length() - 1; left >= 0; --left) {
            for (int right = left; right < s.length(); ++right) {
                if (s[left] == s[right]) {
                    if (right - left <= 1) {
                        records[left][right] = true;
                    } else if (records[left + 1][right - 1]) {
                        records[left][right] = true;
                    }
                }

                if (records[left][right] && right - left > max_size) {
                    max_size = right - left;
                    left_position = left;
                }
            }
        }

        return s.substr(left_position, max_size + 1);
    }
};

通过双指针从前向后依次统计，时间复杂度 O ( n 2 ) O(n^2) O(n2)，空间复杂度 O ( 1 ) O(1) O(1)：

class Solution {
public:
    
    void symmetricallyGrow(const string &s, int left, int right, int &left_position, int &max_length) {
        int i = left;
        int j = right;

        while (i >= 0 && j < s.length() && s[i] == s[j]) {
            if (j - i + 1 > max_length) {
                max_length = j - i + 1;
                left_position = i;
            }
            --i;
            ++j;
        }
    }

    string longestPalindrome(string s) {
        int max_length = -1;
        int left_position;

        for (int pivot = 0; pivot < s.length(); ++pivot) {
            symmetricallyGrow(s, pivot, pivot, left_position, max_length);
            symmetricallyGrow(s, pivot, pivot + 1, left_position, max_length);
        }

        return s.substr(left_position, max_length);
    }
};