LeetCode——Longest Palindromic Substring

shevy 發布于2019-08-23 18:26 / 1682人閱讀

摘要：題目即求最長回文子序列原題鏈接此篇博客僅為學習記錄我的解法及代碼暴力解決，用及進行兩層遍歷循環中套一層循環，用遍歷，求最長回文序列字符串，同時用變量記錄最長子序列這種寫法很暴力，效率很低，一層循環，一層循環，回文序列對比一層，時間復雜度為辣

題目：

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:
Input: "cbbd"
Output: "bb"
即求最長回文子序列
原題鏈接：https://leetcode.com/problems...
此篇博客僅為學習記錄

我的解法及代碼

暴力解決，用outP及innerP進行兩層遍歷：outP循環中套一層for循環，用innerP遍歷，求最長回文序列字符串，同時用logest變量記錄最長子序列

這種寫法很暴力，效率很低，outP一層循環，innerP一層循環，回文序列對比一層，時間復雜度為n^3
辣雞代碼

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let strL = s.length,
        longest = 0,
        resultS = "";
    for(let outP = 0; outP < strL; outP ++){
        for(let innerP = outP + longest; innerP < strL; innerP++){
            let tempS = s.slice(outP, innerP + 1),
                tempSL = tempS.length,
                halfL = parseInt(tempSL/2),
                sub1 = null,
                sub2 = tempS.slice(halfL, tempSL);
            if(tempSL % 2 === 0){
                sub1 = tempS.slice(0, halfL)
            }else{
                sub1 = tempS.slice(0, halfL + 1)
            }
            // console.log("halfL：" + halfL);
            // console.log("tempS：" + tempS);
            // console.log("sub1：" + sub1);
            // console.log("sub2：" + sub2);
            // console.log("------------------")
            if(compareReverse(sub1, sub2)){
                longest = tempSL;
                resultS = tempS;
            }
        }
    }
    return resultS;
};
function compareReverse(s1, s2){
    let length = s1.length,
        half = Math.ceil(length),
        flag = true;
    for(let i = 0; i < half; i++){
        if( !(s1[i] === s2[length-1-i])){
            flag = false;
            break;
        }
    }
    return flag;
}

學習高效的解法

主要學習了兩種，一種是常規的中心檢測法，時間復雜度為n^2，一種是Manacher"s Algorithm 馬拉車算法，時間復雜度為n。
這里主要學習高效的馬拉車寫法

學習及參考鏈接在此：最長回文子串——Manacher 算法

中心檢測法缺點 1.對奇數字符串與偶數字符串需要進行處理

奇偶數會為處理帶來一些麻煩，但是對算法的效率影響不大

2.子串重復訪問

例如babad字符串：

str:    a b c b a b a
index:  0 1 2 3 4 5 6

使用中心檢測法，當index = 2時，訪問了abcba，當index = 3時，訪問了cba，abcba后半串的cba又被訪問了一次

解決方法 1.針對奇偶問題

在字符串中插入"#"（當然其他字符也可以），這樣無論是奇數還是偶數，所有的字符串長度都會變為奇數

例子1：abc -> #a#b#c#
例子2：abcd -> #a#b#c#d#

2.針對重復的問題

核心思想：利用以計算的回文子串長度再進行擴充。
此篇博文寫得很好易懂，推薦：最長回文子串——Manacher 算法

新寫的代碼

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let s2 = getS2(s),
        R = getR(s2),
        maxRight = 0, //記錄最右邊界
        pos = 0,  //記錄最右邊界時對應的中心位置
        maxIndex = 0; //記錄最長回文串對應的下標
    s2.forEach((e, i)=>{
        if(i < maxRight){ //在MR左邊
            const j = 2 * pos - i;
            R[i] = Math.min(maxRight - i, R[j]);//保證回文的情況下，包裹于已探索區域內
            let lp = i - R[i],
                rp = i + R[i];
            while(s2[lp] === s2[rp] && lp >= 0 && rp < s2.length){
                lp--;
                rp++;
                R[i]++;
            }
            if(rp > maxRight){
                pos = i;
            }
        }else{//在MR右邊，包括同MR同一個位置
            let lp = i - 1,
                rp = i + 1;
            while(s2[lp] === s2[rp] && lp >=0 && rp < s2.length){
                lp--;
                rp++;
                R[i]++;
            }
            pos = i;
            maxRight = rp;
        }
        maxIndex = R[i] > R[maxIndex]? i:maxIndex;
    });
    let subArray = s2.slice(maxIndex - R[maxIndex] + 1, maxIndex + R[maxIndex]),
        result = "";
    for(let item of subArray){
        if(item !== "#"){
            result += item
        }
    }
    // console.log(result);
    return result;
};
function getS2(s){//獲得插入"#"后的字符串
    const sLength = s.length,
          s2Length = 2 * sLength + 1;
    let s2 = new Array(s2Length).fill("#");
    for(let j = 1, i = 0; j < s2Length; j=j+2, i++){
        s2[j] = s[i];
    }
    return s2;
}
function getR(s2){//創建回文字符串半徑數組
    let R = new Array(s2.length).fill(1);//初始值為1；
    return R;
}

結果

僅僅超過60%，沉默.jpg，還有很多地方可以優化

云服務器 GPU云服務器 Palindromic Longest LeetCode Substring

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/105218.html

[Leetcode] Longest Palindromic Substring 最長回文子字符串

摘要：這種解法中，外層循環遍歷的是子字符串的中心點，內層循環則是從中心擴散，一旦不是回文就不再計算其他以此為中心的較大的字符串。 Longest Palindromic Substring Given a string S, find the longest palindromic substring in S. You may assume that the maximum length ...

KnewOne 2019-08-14 12:17 評論0 收藏0
LeetCode-5 Longest Palindromic Substring

摘要：題目解析題目是要找出最長的回文字符串，拿到題目的第一反應是遍歷子串，然后一直替換最長的子字符串即可了。但是這種解法遇到極端輸入狀況就會超時，指定的最長長度為，遍歷子串需要兩次循環，判斷回文需要一次循環，所以總的效率為，那么極端狀況會超時。題目 Given a string s, find the longest palindromic substring in s. You may ...

psychola 2019-08-16 13:53 評論0 收藏0
Leetcode 5 Longest Palindromic Substring 最長回文子串

摘要：難度題目是說給出一個字符串求出這個字符串的最長回文的子串回文是指前后完全對稱的字符串像是之類的都算是回文奇數字母的回文和偶數字母的回文中心是不一樣的奇數字母比如的中心在中間字母上偶數字母比如的回文在中間兩字母的中心上由此可見回文中心點實際上 Given a string s, find the longest palindromic substring in s. You may as...

NotFound 2019-08-14 17:12 評論0 收藏0
leetcode 5 Longest Palindromic Substring Java &

摘要：回文的意思就是反轉字符串后和原字符串相等。因為這種想法沒次都是兩邊同時擴展。所以要分目標字符串長度為奇數目標字符串為偶數兩種情況。題目詳情 Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.題目的意思是輸入...

JessYanCoding 2019-08-15 14:27 評論0 收藏0
leetcode5 Longest Palindromic Substring 最長且為回數的子字符

摘要：思路二指針最大長度現在我們從回數的特點入手。因此，假設當前得到的回數的最大長度為，我們可以判斷或者是不是回數。假設此時指針指向，而已知最大回數子字符串的長度為。題目要求 Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s i...

Imfan 2019-08-14 18:01 評論0 收藏0