[数据结构与算法]每日一题_动态规划_5_最长回文子串

前言

为了提升自己的机试水平，故坚持每日一题(尽量吧…

汇总: 每日一题系列_算法提升

题目

题目来源： 5. 最长回文子串(leetcode)
给你一个字符串 s，找到 s 中最长的回文子串。

题解

互文，有两种情况，

• 一种是如 aba, 奇数个字符, 从同一个字符b处的位置扩展
• 另一种是如 baab, 偶数个字符， 分别从两个a处的字符扩展

状态转移方程:
$$?\begin{array}{rl}dp[i,i]& =true\\ dp[i,i+1]& =(S_i==S_j)\\ dp[i,j]& =dp[i+1,j?1]\&(S_i==S_j)\end{array}$$

由此主循环for一下子串下标，每一个下标 i 向两边扩展一下, 在判断是不是比当前最长的还长，如果是，记住前后下标即可(当然也可以记住开始下标和长度)

这里给个$O(n^2)$时间复杂度的解法, 有 Manacher 算法 是 $O(n)$, 这里暂时不去研究了，看到了leetcode题解原话: “然而本算法十分复杂，一般不作为面试内容。这里给出，仅供有兴趣的同学挑战自己.”

class Solution {
private:
    pair<int, int>  expandFromCenter(const string& s, int left, int right) {
        while(left >= 0 && right < s.size() && s[left] == s[right]) {
            left--; // 向左扩展
            right++;  // 向右扩展
        }
        return {left + 1, right - 1}; // 减去多跑一轮循环导致偏差1
    }
public:
    string longestPalindrome(string s) {
        int begin = 0, end = 0;
        for (int i = 0; i < s.size(); i++) {
            // 第一种情况，奇数个子串
            auto [l1, r1] = expandFromCenter(s, i, i);
            // 第二种情况， 偶数个子串
            auto [l2, r2] = expandFromCenter(s, i, i + 1);

            // 判断这两种情况会不会产生更长的互文子串
            if (r1 - l1 > end - begin) {
                begin = l1;
                end = r1;
            }
            if (r2 - l2 > end - begin) {
                begin = l2;
                end = r2;
            }
        }
        // substr(startIndex, length)
        return s.substr(begin, end - begin + 1);
    }
};