菜园前端

Appearance

5. 最长回文子串 ​

原文题目

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

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

题目分析 ​

题目中的意思就是给出一个字符串，要求其正序和反序都是相同的子串，并且是最长的一串。假设现在有一个字符串 babcc ，通过肉眼可发现 bab cc 这种是符合题目要求的，因为 bab 反序之后还是 bab，cc 反序之后还是 cc，但是要取最长的一串，所以结果是 bab。

题解思路 ​

方式一：结合中心扩展和马拉车算法实现 ​

单纯使用中心扩展时间复杂度太高，基本上和暴力破解没有什么区别。其实可以通过马拉车算法的对称性质，遍历一遍字符串即可，遍历字符串的过程中对每一个字符与右侧第一位和第二位进行匹配是否对称，是话将其下标范围记录到数组中，然后继续遍历，如果遍历的字符刚好在这些范围右侧边缘，则进行中心扩展算法。最后只需要在范围数组中找出最长的一组即可。

时间复杂度：O(n)

空间复杂度：O(1)

js
const longestPalindrome = function (s) {
    // 极端情况处理
    if (s.length < 3) {
        return s[0] === s[1] ? s : s[0]
    }

    const arr = []

    for (let p2 = 0; p2 < s.length; p2++) {
        // 1. 当前值和右侧值相等，例如 bb
        if (s[p2] === s[p2 + 1]) {
            arr.push([p2, p2 + 1])
        }

        // 2. 当前值和右侧的右侧值相等，例如 bab
        if (s[p2] === s[p2 + 2]) {
            arr.push([p2, p2 + 2])
        }

        // 3. 判断当前是否在滑动窗口右侧，进行中心扩展
        for (let j = 0; j < arr.length; j++) {
            const [lIndex, rIndex] = arr[j]

            if (p2 === rIndex) {
                const lVal = s[lIndex - 1]
                const rVal = s[rIndex + 1]

                if (lVal && rVal && lVal === rVal) {
                    arr[j] = [lIndex - 1, rIndex + 1]
                }
            }
        }
    }

    // 截取最长窗口
    let s2 = ''
    for (let j = 0; j < arr.length; j++) {
        const [lIndex, rIndex] = arr[j]

        const lVal = s[lIndex]
        const rVal = s[rIndex]

        if (lVal === rVal) {
            if (rIndex + 1 - lIndex > s2.length) {
                s2 = s.slice(lIndex, rIndex + 1)
            }
        }
    }

    // 没有匹配到范围
    if (arr.length === 0) {
        return s[0]
    }

    return s2
}

longestPalindrome('baabbaabb')
const longestPalindrome = function (s) {
    // 极端情况处理
    if (s.length < 3) {
        return s[0] === s[1] ? s : s[0]
    }

    const arr = []

    for (let p2 = 0; p2 < s.length; p2++) {
        // 1. 当前值和右侧值相等，例如 bb
        if (s[p2] === s[p2 + 1]) {
            arr.push([p2, p2 + 1])
        }

        // 2. 当前值和右侧的右侧值相等，例如 bab
        if (s[p2] === s[p2 + 2]) {
            arr.push([p2, p2 + 2])
        }

        // 3. 判断当前是否在滑动窗口右侧，进行中心扩展
        for (let j = 0; j < arr.length; j++) {
            const [lIndex, rIndex] = arr[j]

            if (p2 === rIndex) {
                const lVal = s[lIndex - 1]
                const rVal = s[rIndex + 1]

                if (lVal && rVal && lVal === rVal) {
                    arr[j] = [lIndex - 1, rIndex + 1]
                }
            }
        }
    }

    // 截取最长窗口
    let s2 = ''
    for (let j = 0; j < arr.length; j++) {
        const [lIndex, rIndex] = arr[j]

        const lVal = s[lIndex]
        const rVal = s[rIndex]

        if (lVal === rVal) {
            if (rIndex + 1 - lIndex > s2.length) {
                s2 = s.slice(lIndex, rIndex + 1)
            }
        }
    }

    // 没有匹配到范围
    if (arr.length === 0) {
        return s[0]
    }

    return s2
}

longestPalindrome('baabbaabb')
思路分析

  1. 定义字符串 baabbaabb，开始进行遍历。

  2. 遍历第一个字符是 b

  1. 遍历第二个字符 a
  1. 遍历第三个字符 a

  1. 以此类推，反反复复其实只需要做三件事情。判断当前字符是否与右侧和右侧第二位字符串相等，判断当前字符是否在某一个滑动窗口的右侧边缘。

  2. 最终滑动窗口效果如下。

更新时间: