题解 | #最长回文子串#

/**
 * 解法一：动态规划
 * 思路：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
 * 时间复杂度：O(n^2)，其中 n 是字符串的长度。动态规划的状态总数为 O(n^2)，对于每个状态，我们需要转移的时间为 O(1)。
 * 空间复杂度：O(n^2)，即存储动态规划状态需要的空间。
 */
export function getLongestPalindrome(A: string): number {
    const len = A.length
    if (len < 2) return len

    let maxLen = 1
    let begin = 0
    // dp[i][j] 表示 s[i..j] 是否是回文串
    const dp: boolean[][] = []
    for (let i = 0; i < len; i++) {
        dp[i] = []
    }
    // 初始化：所有长度为 1 的子串都是回文串
    for (let i = 0; i < len; i++) {
        dp[i][i] = true
    }
    const charArray = A.split('')
    // 递推开始
    // 先枚举子串长度
    for (let L = 2; L <= len; L++) {
        // 枚举左边界，左边界的上限设置可以宽松一些
        for (let i = 0; i < len; i++) {
            // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
            let j = L + i - 1
            // 如果右边界越界，就可以退出当前循环
            if (j >= len) break

            if (charArray[i] != charArray[j]) {
                dp[i][j] = false
            } else {
                if (j - i < 3) {
                    dp[i][j] = true
                } else {
                    dp[i][j] = dp[i + 1][j - 1]
                }
            }

            // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
            if (dp[i][j] && j - i + 1 > maxLen) {
                maxLen = j - i + 1
                begin = i
            }
        }
    }
    
    return A.substring(begin, begin + maxLen).length
}

/**
 * 解法二：中心扩展算法
 * 思路：如果是回文子串，那么它的左右两边的元素肯定是对称的，我们可以使用左右指针，从当前元素向两边扩散，以找到最长字串。
 * 时间复杂度：O(n^2)。
 * 空间复杂度：O(1)。
 */
export function getLongestPalindrome(A: string): number {
    let res = 0
    for (let i = 0; i < A.length; i++) {
        const str1 = palindrome(A, i, i)
        const str2 = palindrome(A, i, i + 1)
        res = Math.max(res, str1.length, str2.length)
    }
    return res
};
function palindrome(s: string, left: number, right: number): string {
    // 左右指针，从s[l]和s[r]向两边扩散，找到最长回文串
    while (left >= 0 && right < s.length && s[left] === s[right]) {
        left--
        right++
    }
    return s.substr(left + 1, right - left - 1)
}

一站式解决前端面试高频算法题

https://github.com/hovinghuang/fe-agorithm-interview