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] 的值即可。

而我個人的方法是 先确定目前值可能産生的回文範圍，加大了計算消耗，而範圍又不止一個，又加大了消耗，是以導緻性能遠遠不如最優解法。