LeetCode5最长回文子串（javascript解析）

题目描述

题目难度：中等

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：
输入: "cbbd"
输出: "bb"
           

个人解题思路

1.循环遍历字符串，设置当前字符

2.找到所有后面和当前当前的字符相同的字符

3.从找到的字符中取位置最靠后的字符，取两个字符中间的字符串

4.依次比较取出的字符串中0&n,1&n-1,2&n-2 依次比较一次不相等即不符合要求，如都相等保存起来，否则重复3。

5.重复2，3，4

6.最后取出所有保存下来的字符串中最长的一个

代码如下

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let currentString = '';
    let currentFindAry = [];
    let resultAry = [];
    for(let i = 0; i < s.length; i ++) {
        currentString = s[i];
        currentFindAry = findNextString(currentString, s.slice(i), i);
        if(currentFindAry.length > 0) {
            for(let j = 0; j < currentFindAry.length; j ++) {
                let targetString = s.slice(i + 1, currentFindAry[j]);
                if(compareString(targetString)) {
                    resultAry.push(currentString + targetString + currentString);
                    break;
                }
            }
        }
    }
    if(resultAry.length > 0) {
        let resultString = '';
        for(let i = 0; i < resultAry.length; i ++) {
            if(resultAry[i].length > resultString.length) {
                resultString = resultAry[i];
            }
        }
        return resultString;
    }else {
        if(!s) {
            return '';
        }else {
            return s[0];
        }
    }
    
};

function compareString(string) {
    for(let i = 0; i < string.length / 2; i ++) {
        if(string[i] !== string[string.length - i - 1]) {
            return false;
        }
    }
    return true;
}

function findNextString(currentString, allString, currentNum) {
    let result = [];
    for(let i = allString.length - 1; i > 0; i --) {
        if(currentString === allString[i]) {
            result.push(i + currentNum);
        }
    }
    return result;
}
           

思考&实现总用时：约12分钟

运行结果

执行结果：通过
执行用时 :700 ms, 在所有 javascript 提交中击败了14.21%的用户
内存消耗 :50.2 MB, 在所有 javascript 提交中击败了20.37%的用户
           

虽然通过了测试用例，但是从运行结果上来看，实在是非常不理想，

运行的时间复杂度O(n³)，且多次使用slice方法增加了消耗

最优解法

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
	var s_len=s.length;
	if(s_len<2){
    	return s;
    }
	var string=s[0];
    var s_len_1=s_len-1;
    var start=0;
    var end=0;
    for(var i=0;i<s_len_1;i++){
    	let this_end_i=i;
    	while(this_end_i<s_len_1&&s[this_end_i]==s[this_end_i+1]){
    		this_end_i++
    	}
    	let i2=this_end_i;
    	while(i>0&&this_end_i<s_len_1&&s[i-1]==s[this_end_i+1]){
    		i--
    		this_end_i++
    	}
    	if(this_end_i-i>end-start){
    		start=i;
    		end=this_end_i;
    	}
    	i=i2;
    }	
    string=s.slice(start,end+1);
    return string;
};
           

最优解法解析

先吐槽下这段代码用了命名很多 _ 以及代码中很多 - 且中间没有空格 看起来十分不爽。

最优解法的核心思路在于从当前指向的字符向该字符两边去扩散比较

如 babad 遍历到 s[1] 去比较 s[0] 和 s[1] 的值即可。

而我个人的方法是 先确定当前值可能产生的回文范围，加大了计算消耗，而范围又不止一个，又加大了消耗，所以导致性能远远不如最优解法。