5.longest-palindromic-substring.md

5. 最长回文子串

https://leetcode-cn.com/problems/longest-palindromic-substring/

• 5. 最长回文子串
  • 题目描述
  • 方法1：中心扩展
    • 思路
    • 复杂度分析
    • 代码

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法1：中心扩展

思路

最简单的思路，以 单个 或者 两个一组相同 的字符为中心，向左右两侧扩展，找到以这个(或者这两个)字符为中心的最长回文子串。接着对 s 中的所有字符重复这个操作，记录这个过程中找到的最长回文子串。

复杂度分析

• 时间复杂度：$O(N^2)$。
• 空间复杂度：$O(1)$。

代码

JavaScript Code

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
    // 中心扩展，有两种情况：
    // 1. 对于每个单个字符，向两侧扩展
    // 2. 对于每组两个相同的字符，向两侧扩展

    let ans = '';
    for (let i = 0; i < s.length; i++) {
        const str1 = expand(s, i, i);
        if (str1.length > ans.length) ans = str1;

        if (s[i] === s[i + 1]) {
            const str2 = expand(s, i, i + 1);
            if (str2.length > ans.length) ans = str2;
        }
    }
    return ans;

    // **************************************************
    function expand(s, l, r) {
        while (l >= 0 && r < s.length && s[l] === s[r]) {
            l--;
            r++;
        }
        return s.slice(l + 1, r);
    }
};

更多题解可以访问：https://github.com/suukii/91-days-algorithm