Leetcode 编程训练[5]:Longest Palindromic Substring

#5:这次的题目的要求是在字符串中找到最长的回文字符串。例如在'abcxzcvczxziua'中获得'xzcvczx'。首要的是解决问题,回文的形式有两种:一种ABCBA型,中间有一个单独的字符,字符串总长为奇数;另一种ABCCBA型,中间的字符也会重复一遍,这样的回文字符串总长为偶数。我们需要人为地区分这两种情况。程序先检测字符是否与后一位字符一样,如果一样则判断为回文,进入一个循环来确定这个回文的大小。最后输出结果就行了。

/**
 * @param {string} s
 * @returns {string}
 */
var longestPalindrome = function(s) {
    var lenPalindrome = 1;
    var palindromeStr = s.charAt(0);
    var lenS = s.length;
    for(var i = 0; i < lenS; i++){
        if(s.charAt(i) === s.charAt(i+2)){
            var plus = 1;
            while(i - plus >=0 && s.charAt(i - plus) == s.charAt(i + plus + 2)){
                plus++;
            }
            if(2 * plus + 1 >= lenPalindrome){
                lenPalindrome = 2 * plus + 1;
                palindromeStr = s.substr(i + 1 - plus, 2 * plus + 1);
            }
        }
        if(s.charAt(i) === s.charAt(i+1)){
            var plus = 1;
            while(i - plus >=0 && s.charAt(i - plus) == s.charAt(i + plus + 1)){
                plus++;
            }
            if(2 * plus >= lenPalindrome){
                lenPalindrome = 2 * plus;
                palindromeStr = s.substr(i + 1 - plus, 2 * plus);
            }
        }
    }
    return palindromeStr;
};

网上有人谈论比较快速的方法是将小回文组合成大回文。比如100字长的回文为98字长的回文组成。在这个基础下,历遍字符串时向字符前端查找指定长度的回文,如果存在则更新为这个回文。

runtime

源码