[leetcode - Bliend-75 ] 5. Longest Palindromic Substring (Me

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

给一个 string 回传该 string 最长的 palindromic substring.

Example

Input: s = "babad"
Output: "bab" || "aba"

Input: s = "cbbd"
Output: "bb"

Thanking

目的是要找到最长的 palindromic substring，可以使用 for 迴圈把每一个 substring 找出来并判断哪一个是最长的，[[b], [ba], [bab], [baba], [babad], [a], [ab], [aba], ....] 但这种方法的时间複杂度为 O(n^3) 太慢了，所以可以用 dynamic programming 减少时间複杂度。

Step

基数

指定一个 chart 后检查他的左右边的 chart 是否是相等的

如果是一样的就在往旁边检查

如果找到两边不相等的时候则代表这个 palindromic substring 的长度。

偶数

指定一个 chart 后检查他旁边的 chart 是否相等

如果相等则在往旁边检查

一直往旁边移动直到找到这个 chart 和指定的 chart 不同的时候就代表这个 palindromic substring 的长度。

Coding

var longestPalindrome = function (s) {    let res = [0, 1];    for (let i = 0; i < s.length; i++) {        const even = helper(i - 1, i, s);                           // (1)        const odd = helper(i - 1, i + 1, s);                        // (2)        const type = even[2] > odd[2] ? even : odd;                 // (3)        res = res[1] - res[0] > type[1] - type[0] ? res : type;     // (4)    }    return s.substring(res[0], res[1]);}function helper(l, r, s) {    if (l < 0 || r > s.length) return [l + 1, r];    while (l >= 0 && r < s.length) {        if (s[l] === s[r]) {            l--;            r++;        } else {            break;        }    }    return [l + 1, r, r - l + 1];                                    // (5)}

(1): 找到偶数的最长 substring(2): 找到基数的最长 substring(3): 比较偶数和基数的 substring 哪一个比较长(4): 将比较长的 substring 暂存 res(5): 如果发现左边的 chart 和右边的 chart 不同则回传 [左边的index, 右边的index, 左右index中间有多少的 chart]

Time complexity: O(n^2)