5. Longest Palindromic Substring

Leetcode

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

題目

Given a string s, return the longest palindromic substring in s.

解答

• 方法一

利用一個二維數組 dp[i][j]，紀錄 i 到 j 是否為迴文

For example

s = 'babad'

dp[0][0] = true;

dp[0][1] = false;

dp[0][2] = true;

dp[0][3] = true;

var longestPalindrome = function(s) {
    const dp = Array.from(Array(s.length), (_) => Array(s.length));
    // 紀錄開始位置
    let left = 0;
    // 紀錄最長迴文長度
    let maxLength = 1;
    
    for(let i=0; i<s.length; i++) {
        // 自己與自己比一定是迴文
        dp[i][i] = true;
        // 對小於 i 的部分遞迴
        // ex. i = 3;
        // 計算 j 從 0 -> 3 範圍的所有 dp 是否為迴文
        // 可以求出 dp[0][3], dp[1][3], dp[2][3]
        for(let j=0; j<i; j++) {
            if(i-j<=1) {
                // 相鄰元素，只要兩者相等為迴文
                dp[j][i] = s[j] === s[i];
            } else {
                // 不相鄰元素，確保兩者相同及 dp 向內減 1 為迴文，即為迴文
                dp[j][i] = s[j] === s[i] && dp[j+1][i-1];
            }
            if(dp[j][i] && i-j+1 > maxLength) {
                left = j;
                maxLength = i-j+1;
            }
        }
    }
    
    return s.substring(left, left+maxLength);
};

Runtime: 813 ms, faster than 26.86% of JavaScript online submissions for Longest Palindromic Substring.

Memory Usage: 83.7 MB, less than 5.80% of JavaScript online submissions for Longest Palindromic Substring.

• 方法二

一一遍歷所有元素，並往左右查看是否元素相等達成迴文條件，此時需考慮所有元素為奇數或偶數的狀況

var longestPalindrome = function(s) {
    let res = s[0];
    let maxLength = 1;
    
    for(let i=0; i<s.length; i++) {
        // 奇數 - 丟入的左右元素都為自己
        const lenOdd = getLongestPalindrome(i, i);
        // 偶數 - 丟入自己與右側元素
        const lenEven = getLongestPalindrome(i, i+1);
        const len = Math.max(lenOdd, lenEven);
        if(len > maxLength) {
            // example
            // cabac i=2, len=5, start=0
            // cabbac i=2, len=6, start=0
            const start = i-Math.floor((len-1)/2);
            // console.log(start, i, len)
            res = s.substring(start, start+len);
            maxLength = len;
        }
    }
    return res;
    
    function getLongestPalindrome(left, right) {
        let l = left;
        let r = right;
        
        while(s[l] === s[r] && l >=0 && r < s.length) {
            l--;
            r++;
        }
        return r-l-1;
    }
};

Runtime: 136 ms, faster than 62.75% of JavaScript online submissions for Longest Palindromic Substring.

Memory Usage: 42 MB, less than 57.86% of JavaScript online submissions for Longest Palindromic Substring.

• 方法三

Manacher 算法，待研究...

參考資料

https://www.cnblogs.com/grandyang/p/4464476.html