专栏首页flytam之深入前端技术栈leetcode Problem 5 最长子回文串

leetcode Problem 5 最长子回文串

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

1、暴力做法。 遍历所有的子串,求出最长。复杂度O(n3)。显然GG了。 2、动态规划 把一个大问题分解成每一个小问题进行求解。假设字符串s,则s[i]到s[j]是回文的话,s[i+1]到s[j-1]也是回文;或者说,已知s[i+1]到s[j-1]是回文的情况下,如果s[i]==s[j]则,s[i]到s[j]就是回文,我们用数组table[i][j]来表示i到j的是否回文状态。代码如下,复杂度是o(n2)。

var longestPalindrome = function (s) {
    const length = s.length;
    let table = [];
    for (let i = 0; i < 1000; i++) {
        table[i] = new Array();
        for (let j = 0; j < 1000; j++) {

            table[i][j] = 0;
        }
    }

    let maxlength = 1,
        maxstr,
        longestbegin;
    for (let i = 0; i < length; i++) {
        table[i][i] = 1; //所有的 i 到 i的字符串是回文
        longestbegin = i;        
    }
    for (let i = 0; i < length - 1; i++) {
        //长度为2的回文
        if (s[i] === s[i + 1]){
            table[i][i + 1] = 1;
            maxlength = 2;
            longestbegin = i;
        }

    }
    //状态转移 再table[i+1][j-1] == 1的情况下,如果i === j,则 table[i][j]为1 从长度为3的回文开始
    for (let len = 3; len <= length; len++) {
        for (let i = 0; i < length - len + 1; i++) {
            //遍历所有长度为len的字符串
            let j = i + len - 1;//两种情况 单数回文和双数回文
            //let j = len % 2 === 0?i + len - 2
            if (s[i] === s[j] && table[i + 1][j - 1] === 1) {
                table[i][j] = 1;
                maxlength = len;
                longestbegin = i;
            }
        }
    }
    //console.log(longestbegin, maxlength)
    return s.slice(longestbegin,longestbegin +  maxlength)
};

然而,这里还是过不了leetcode的。显然,还需要优化的地方 好像o(n2)也是能强行过的。。把字符串换成数组再处理。不过时间只优于百分之1的人,太菜了23333

//最长回文串 o(n2)
var longestPalindrome = function (s) {
    const length = s.length;
    s = s.split('');
    let table = [];
    let maxlength = 1,
        maxstr,
        longestbegin = 0;
    for (let i = 0; i < length; i++) {
        table[i] = new Array();
        table[i][i] = 1;
    }
    for (let i = 0; i < length - 1; i++) {
        //长度为2的回文
        if (s[i] === s[i + 1]) {
            table[i][i + 1] = 1;
            maxlength = 2;
            longestbegin = i;
        }
    }
    //状态转移 再table[i+1][j-1] == 1的情况下,如果i === j,则 table[i][j]为1 从长度为3的回文开始
    for (let len = 2; len <= length; len++) {
        for (let i = 0; i < length - len + 1; i++) {
            //遍历所有长度为len的字符串
            let j = i + len - 1; //两种情况 单数回文和双数回文
            //let j = len % 2 === 0?i + len - 2
            if (s[i] === s[j] && table[i + 1][j - 1] === 1) {
                table[i][j] = 1;
                maxlength = len;
                longestbegin = i;
            }
        }
    }
    //console.log(longestbegin, maxlength)
    return s.join('').slice(longestbegin, longestbegin + maxlength)//真的是日了狗。。。数组处理比字符串处理要快
};

而且不是每次都能过,这个还是要优化的啊

换另一种思路,就是。遍历字符串中的每个字符。算出以该字符为中心的最长回文串

var longestPalindrome2 = function (s) {
    function expandAroundCenter(s, l, r) {
        while (l >= 0 && r < sLen && s[l] == s[r]) {
            l--;
            r++;
        }
        return r - l - 1;
    }
    let start = 0,
        end = 0,
        len1 = 0,
        len2 = 0,
        len = 0,
        sLen = s.length;
    for (let i = 0; i < sLen; i++) {

        len1 = expandAroundCenter(s, i, i);//aba这种回文
        len2 = expandAroundCenter(s, i, i + 1);//abba这种回文
        len = Math.max(len1, len2);//算出较大的回文
        if (len > end - start) {
            end = i + (len >> 1);
            start = end + 1 - len;
        }
    }
    return s.substring(start, end + 1);
};

这次就快多了。。。。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 18前端实习面经+offer

    总的来说,该前端面试覆盖的内容还是相当广的,而且非常注重基础(这应该是大厂的一贯风格)。计算机基础课程操作系统、数据结构、计算机网络必须非常扎实,然后前端cs...

    flytam
  • rxjs实现元素拖拽

    1、监听 drag 元素 的 mousedown,回调中设置标识开始拖动,计算出初始点击到元素左上角距离

    flytam
  • 由浅至深了解webpack异步加载背后的原理

    1、module:我们源码目录中的每一个文件,在 webpack 中当作module来处理(webpack 原生不支持的文件类型,则通过 loader 来实现)...

    flytam
  • 【LeetCode题解-005】Longest Palindrome Substring

    Given a string s, find the longest palindromic substring in s. You may assume th...

    周三不加班
  • Python 中argparse模块的使用

    如果脚本很简单或临时使用,没有多个复杂的参数选项,可以直接利用sys.argv将脚本后的参数依次读取(读进来的默认是字符串格式)。

    致Great
  • python分析ip地理位置

    119.128.200.90 218.90.169.90 219.129.242.180 183.69.189.172 222.89.193.18 2...

    py3study
  • 编程思想:巧用位运算重构代码

    巧用位运算能极大的精简代码和提高程序效率。所以,在一些优秀的开源代码中,经常能出现位运算。所以,把位运算这种思想迁移到业务代码里,有时候往往能起到柳暗花明般的重...

    用户1161731
  • Python 中argparse模块的使用

    如果脚本很简单或临时使用,没有多个复杂的参数选项,可以直接利用sys.argv将脚本后的参数依次读取(读进来的默认是字符串格式)。

    用户1332428
  • 在64位系统下,指向int型的指针占的内存空间多大?

    黑泽君
  • fio测试ceph的filestore

    fio是一个适应性非常强的软件,基本上能够模拟所有的IO请求,是目前最全面的一款测试软件,之前在看德国电信的一篇分享的时候,里面就提到了,如果需要测试存储性能,...

    用户2772802

扫码关注云+社区

领取腾讯云代金券