5. 最長回文子串

給你一個字串 s，找到 s 中最長的回文子串，

示例 1：

輸入：s = "babad"
輸出："bab"
解釋："aba" 同樣是符合題意的答案，

示例 2：

輸入：s = "cbbd"
輸出："bb"

提示：

• 1 <= s.length <= 1000
• s 僅由數字和英文字母組成

解法一：暴力

用雙重回圈遍歷字串的所有起始位置與終止位置，然后判斷是否是回文子串，是就更新最長長度和回文的起始位置，方便之后分隔字串成子串，

var longestPalindrome = function(s) {
    //處理特殊情況，長度小于2的就直接回傳
    let len=s.length;
    if(len<2){
        return s;
    }
    
    //初始化最長的回文長度、回文起始下標
    let maxLen=1,begin=0;
    // console.log(s.substri/\ng(begin,begin+maxLen));
    //暴力遍歷所有情況
    for(let i=0;i<len-1;i++){
        for(let j=i+1;j<len;j++){
            //如果長度比之前的長，并且判斷出是回文
            if(j-i+1 > maxLen && validP(s,i,j)){
                //更新長度、起始下標
                maxLen=j-i+1;
                begin=i;
            }
        }
        
    }
    return s.substring(begin,begin+maxLen);
};

//創建一個判斷回文的函式，左右指標往中心靠攏
function validP(s,left,right){
    while(left<=right){
        if(s[left] != s[right]){
            return false;
        }
        left++;
        right--;
    }
    return true;
}

復雜度分析

• 時間復雜度：\(O(n^3)\)，
• 空間復雜度：\(O(1)\)，

解法二：中心擴散

令一個指標在每遍歷一個字串的下標時，創建一個中心擴散函式進行判斷，當左右擴散指標不越界的情況，獲取中心點為奇數或偶數（因為中心點可能為1或2個)長度，接著再選擇出最長的長度，當指標遍歷完后，說明所有的擴散型別都比較完了，

var longestPalindrome = function(s) {
    //處理特殊情況
    let len=s.length;
    if(len<2){
        return s;
    }
    //初始化最長長度和起始位置
    let maxLen=1,begin=0;
    //跟暴力不同，在走向字串末尾時，一次一次地擴散嘗試
    for(let i=0;i< len - 1;i++){
        //考慮奇數與偶數的情況，所以有兩種擴散
        let oddLen=expandAroundCenter(s,i,i);
        let evenLen=expandAroundCenter(s,i,i+1);

        //看看奇數還是偶數的情況大，再比較之前的最長長度
        let curMaxLen=Math.max(oddLen,evenLen);
        if(curMaxLen > maxLen){
            maxLen=curMaxLen;
            //根據公式 i-(回文長度-1)/2 知道起始位置，不過這里注意是要向上取整
            begin=Math.ceil(i-(maxLen-1)/2);
        }
    }
    return s.substring(begin,begin+maxLen);
};

//中心擴散
function expandAroundCenter(s,left,right){
    while(left>=0 && right<s.length && s[left]===s[right]){
        //符合情況的就擴散
        left--,right++;
    }
    //由于先判斷再回圈的while，存在擴散超出回文長度的邊界的情況，剛好變得不再是回文情況，所以是（right-left+1-2），而不是right-left+1
    console.log(right,left)
    return right-left-1;
}

復雜度分析

• 時間復雜度：\(O(n^2)\)，
• 空間復雜度：\(O(1)\)，

解法三：動態規劃

可以知道如果判斷字串是回文子串，那么拋開前后兩端，就由中間決定了以下圖舉例：

我要保證j>i，即右指標要大于左指標，而下面紅線指示的例子就是表示拋開前后兩端看中間又怎么樣，以此回圈，

var longestPalindrome = function(s) {
    let len=s.length;
    if(len<2){
        return s;
    }

    let maxLen=1,begin=0;

    //初始化二維dp，要注意深拷貝和淺拷貝的問題
    let dp=Array.from(new Array(len),()=> new Array(len).fill(false));

    //對角線，即長度為1的子串都是回文串
    for(var i=0;i<len;i++){
        dp[i][i]=true;
    }
    //從列開始數,不用從0開始，因為第0列本身沒比較的價值
    for(var j=1;j<len;j++){
        //只用看右上角的比對情況，所以是i<j，i代表從左端往中間的值，j代表從右端往中間的值
        for(var i=0;i<j;i++){
            //如果左右兩端不匹配就說明不符合
            if(s[i]!=s[j]){
                dp[i][j]=false;
            //如果兩端匹配了
            }else{
                //此時的子串太短或者是沒有的情況，也就沒必要比下去了
                if(j-i<3){
                    dp[i][j]=true;
                //如果還太長，就繼續比下去，左右兩端指標繼續往中間移動
                }else{
                    dp[i][j]=dp[i+1][j-1];
                }
            }
            //最后就不斷更新獲取最長的長度
            if(dp[i][j] && j-i+1>maxLen){
                maxLen=j-i+1;
                begin=i;
            }
        }
    }
    return s.substring(begin,begin+maxLen);
};

復雜度分析

• 時間復雜度：\(O(n^2)\)，其中 \(n\) 是字串的長度，動態規劃的狀態總數為 \(O(n^2)\)，對于每個狀態，我們需要轉移的時間為 \(O(1)\)，
• 空間復雜度：\(O(n^2)\)，即存盤動態規劃狀態需要的空間，

解法四：Manacher演算法（馬拉車演算法）

太難了，后面解決，

標籤：其他

上一篇：歸并排序及優化

下一篇：背包問題