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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let ans = 0,
        ml = 0,
        mr = 0,
        len = s.length;
    for (let l = 0; l < len; l++) {
        for (let r = l + 1; r <= len; r++) {
            let t = s.substring(l, r);
            if (t.split('').reverse('').join('') === t) {
                if (r - l > ans) {
                    ans = r - l;
                    ml = l;
                    mr = r;
                }
            }
        }
    }
    return s.substring(ml, mr);
};

O(n2) 果然超时了
改进后：
这个方法跟Sliding Window方法类似，只是window的变化改为以s[i]为中心扩展伸缩。
Runtime: 100 ms, faster than 88.83% of JavaScript online submissions for Longest Palindromic Substring.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * @param {string} s
 * @return {string}
 */
const expandAroundCenter = (s, l, r) => {
    while (l >=0 && r < s.length && s[l] === s[r]) {
        l--;
        r++;
    }
    return r - l - 1;
}
const longestPalindrome = (s) => {
    if (s.length < 1) {
        return "";
    }
    let start = 0,
        end = 0;
    for (let i = 0; i < s.length; i++) {
        // console.log(s);
        let len1 = expandAroundCenter(s, i, i);
        let len2 = expandAroundCenter(s, i, i + 1);
        let len = Math.max(len1, len2);
        if (len > end - start) {
            // console.log(i, len);
            start = i - Math.floor((len - 1) / 2);
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
};