LeetCode——Longest Palindromic Substring

shevy 发布于2019-08-23 18:26 / 1674人阅读

摘要：题目即求最长回文子序列原题链接此篇博客仅为学习记录我的解法及代码暴力解决，用及进行两层遍历循环中套一层循环，用遍历，求最长回文序列字符串，同时用变量记录最长子序列这种写法很暴力，效率很低，一层循环，一层循环，回文序列对比一层，时间复杂度为辣

题目：

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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