专栏首页异名异名解题: 最长回文子串

异名解题: 最长回文子串

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

测试用例一 输入: "babad" 输出: "bab" ("aba" 也是一个有效答案) 测试用例二 输入: "cbbd" 输出: "bb"

解题思路

方法一O(n³): 暴力遍历

N个符合条件的字符串,等于前N-1个字符串加上第N个字符然后取反,那么这个字符串就是回文字符串。它只能找出从头开始的字符,所以还得在外层添加一个循环,更改字符串的起点。以下就是该解法写出来的函数,递归部分复杂度是O(n²),然后外层再套一个N层的遍历,所以它的复杂度是O(n³)。

function longestPalindrome(str) {
    let idx = 0;
    let startIdx = 0;
    let len = str.length;
    let maxSubStr = str[0];
    let curStr = '';
    if (len <= 1) return str;

    while(startIdx < len - 1) {
        curStr = str[startIdx]
        idx = startIdx
        function loop() {
            while (idx < len - 1) {
                idx++;
                curStr = curStr + str[idx]
                if (curStr.split('').reverse().join('') == curStr && curStr.length >= maxSubStr.length) {
                    maxSubStr = curStr;
                }
                loop()
            }
        }
        loop()
        startIdx+=1;
    }

    return maxSubStr
}

但是在LeetCode上提交的时候,第41个用例超时了。该用例的长度为877,我本地在不限时间地跑该用例的耗时是3569.156ms,最长回文子串为fklkf;总结一下问题主要是由于递归解法的效率比较低,函数重复嵌套调用,而且并没有提炼出相同的子问题

方法二O(n²):动态规划/中心扩展

方法一执行超时之后换种指导思想,往动态规划方向想,想到的第一个状态转移方程是F(n+1) == str[n-1]+F(n)+str[n+1] 且满足 str[n+1] == str[n-1]。它刚好可以用递推来实现,因为每个单独的字母都是一个符合条件的答案,然后往左右递增扩展,如果左右相同,那就能够得出下一个回文,直到找到最长的回文。但是这样解的话还要区分两种情况,如果回文的长度是基数,比如cabad的输出是aba,它的中心位是一个字母,但是如果回文的长度是偶数,比如abbc的输出是bb,那它的中心位就是两个字母,所以使用这个方法得分别对这两种情况做处理,下面的代码就是基于这种解法而来,官方解法更简洁

function longestPalindrome(str) {
    if (str.length < 2) return str;
  
    let maxStr = str[0];
    for (let curIdx = 0; curIdx < str.length - 1; curIdx++) {
      let str1 = search(str, curIdx, true);
      let str2 = search(str, curIdx, false);
      let result = str1.length > str2.length ? str1 : str2;
      maxStr = result.length > maxStr.length ? result : maxStr;
    }
    return maxStr;
  }
  
  function search(str, curIdx, isEven) {
    let prevIdx, nextIdx;
    let result = str[curIdx];
  
    if (isEven) {
      if (str[curIdx] == str[curIdx + 1]) {
        result += str[curIdx + 1];
      } else {
        return result;
      }
    }
  
    let maxLoopTime = Math.min(str.length - curIdx, curIdx);
    for (let n = 1; n <= maxLoopTime; n++) {
      prevIdx = curIdx - n;
      nextIdx = isEven ? curIdx + n + 1 : curIdx + n;
      if (str[prevIdx] != str[nextIdx] || str[prevIdx] == undefined) break;
      result = str[prevIdx] + result + str[nextIdx];
    }
  
    return result;
  }

方法二可以改良,上面的逻辑针对回文中心是一个字母的和两个字母两种情况分别做了处理,如果取巧一点,往字符串前后,以及每个字母之间插入一个#,就能够把回文中心是两个字母的情况给去掉,比如cabad插入后变成#c#a#b#a#d#,它的输出是#a#b#a#,回文中心还是字母;abbc插入后变成#a#b#b#c#,它的输出是#b#b#,回文中心变成了#也是一个字母,在这个基础上使用中心扩展就不用考虑两种情况了,这其实也是马拉车算法的第一步。

本文分享自微信公众号 - 异名(async-code),作者:异名君

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-06-07

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 游戏性能优化

    异名最近负责了一个微信小游戏的项目,在版本迭代间隙对游戏的性能调优进行了一次尝试。这个游戏是个打击类游戏,下面展示一下游戏的预览效果?

    异名
  • Cocos游戏开发入门最佳实践

    因为公司的业务需求,近期学习了CocosCreator这款游戏引擎的开发,也基于此上线了一款游戏,因此写这系列文章记录一下我从入门到项目发布的学习过程。

    异名
  • 移动残影效果

    游戏中的人物移动带起残影,用来表达速度是很有视觉表现力的。异名的实现思路是从“白玉无冰”那里参照过来的,在具体的实现上面添加了一些异名自己的理解。

    异名
  • 从C#到TypeScript - 变量

    从C#到TypeScript - 变量 TypeScript的变量声明和ES6差不多,相比之前主要是多了let和const 为什么不用var 不管是TypeSc...

    用户1147588
  • JS中的字符串方法

    str.lastIndexOf(start)// " Index " 的 " I " 大写

    我不是费圆
  • Foundation-String

    最近写完了Swift 3.0教程 ,在接下来这段时间,继续写Foundation 的教程,帮助大家更加深入,系统的学习Foundation 框架,可能会持续一段...

    酷走天涯
  • ES6

    ES的全称是ECMAScript,它是由ECMA国际标准化组织制定的一项脚本语言的标准化规范。

    eadela
  • Dart字符串判空

    NullPointerExp是无数java程序员都想消除的问题,OC里,nil对象调方法返回的是nil(这种做法,仁者见仁,智者见智);kotlin和swift...

    DSoon
  • var、let、const

    变量使用:创建(create)、初始化(initialize) 和赋值(assign)。

    城市中的游牧民族

扫码关注云+社区

领取腾讯云代金券