最长回文子串

1.0 快乐的n³算法

var longestPalindrome = function(s) {
    var max = 0;
    var start = 0;
    for(var i = 0; i < s.length; ++i) {
        for(var j = i; j < s.length; ++j) {
            if(isPalindrome(s, i, j))  {
                if((j-i+1) >= max){
                    max = (j-i+1);
                    start = i;
                }
            }
        }
    }
    return s.substr(start, max);
};

var isPalindrome = function(s, start, end) {
    for(var i = start; i < end; ++i) {
        if(s[i] != s[end-i+start]){
            return false;
        }
    }
    return true;
};

枚举所有子字符串n²，因为不是子序列问题，所以不是n!。

2.0 n²

var longestPalindrome = function(s) {
    var maxl = 0;
    var start = -1;
    for(var i = 0; i < s.length; ++i) {
        var j = 0;
        for(; (i-j>=0) && (i+j < s.length); ++j) {
            if(s[i-j] != s[i+j]){
                break;
            }
        }
        j -= 1;
        if(maxl < 2*j+1) {
            maxl = 2*j+1;
            start = i-j;
        }
        var k = 0;
        for(; i-k >= 0 && i+k+1 < s.length; ++k) {
            if(s[i-k] != s[i+k+1]){
                break;
            }
        }
        k -= 1;
        if(maxl < 2*k+2) {
            maxl = 2*k+2;
            start = i-k;
        }
    }
    return s.substr(start, maxl);
};

遍历一次所有元素，以它为中心向左右扫描找到当前数字为中心的最长字符串。需要考虑字符串为奇数或偶数的情况。