leetcode解题系列-最长回文子串最全解法

栏目: 编程工具 · 发布时间: 5年前

内容简介:第一次写文章,有不当之处还望各位大佬指出。很显然,此解法虽然最终能够得到结果,但是效率很低,在这个讲究高效编程的时代,这种方法是不可取的。 (此方法由于时间复杂度太高,在leetcode上提交时会提示 Time Limit Exceeded,并且提交不了)1.最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。

本人是一个一名前端菜:chicken:,正在努力加班加点学习中,看着大佬们写的文章、demo啥的,羡慕不已。盼望着大佬们哪天能给个内推机会啥的那就nice了。 最近刷leetcode刷到这个题目,也在网上看到了各种各样的解法,于湿乎我也尝试着写文章,记录一下学习中值得分享的内容

第一次写文章,有不当之处还望各位大佬指出。

问题描述

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

    示例 1:

    输入: “babad”

    输出: “bab”

    注意: “aba” 也是一个有效答案。

    示例 2:

    输入: “amnbvcxzzxcvbnmb”

    输出: “mnbvcxzzxcvbnm”

分析与求解

第一种 暴力解法

最容易想到的就是暴力解法,即外面的两层循环找到所有子串,第三层循环判断子串是否是回文。方法的时间复杂度为O(n^3),空间复杂度为O(1)。

var longestPalindrome = function (s) {
  let n = s.length;
  if(n == 0) return ''; //字符串为空则返回空
  if(n == 1) return s;  //字符串为一个字符, 显然返回自身
  let result = ''
  for (let i = 0; i < n; i++) { //字符串长度超过2
    for (let j = i + 1; j <= n; j++) {
      let str = s.slice(i, j); //可得到所有子串
      let f = str.split('').reverse().join(''); //对字符串利用数组方法倒序

      if (str == f) { //判断是否为回文
        result = str.length > result.length ? str : result;
      }
    }
  }
  return result;
}
console.log(longestPalindrome(str))

复制代码

很显然,此解法虽然最终能够得到结果,但是效率很低,在这个讲究高效编程的时代,这种方法是不可取的。 (此方法由于时间复杂度太高,在leetcode上提交时会提示 Time Limit Exceeded,并且提交不了)

第二种 动态规划

动态规划(Dynamic Programming)是一种分阶段求解决策问题的数学思想。总结起来就是一句话,大事化小,小事化了。

能采用动态规划求解的问题的一般要具有3个性质:

1.最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。

2.无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。

3.有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势

大概了解了一下动态规划,下面让我们来看具体代码

var longestPalindrome = function(s) {
    let len = s.length;
    let result;
    let i,j,L;
    let dp=Array(len).fill(0).map(x=>Array(len).fill(0));
    //console.log(dp);
    if(len<=1){
        return s
    }
    // 只有一个字符的情况是回文
    for(i = 0;i<len;i++){
        dp[i][i] = 1
        result = s[i]
    }

    // L是i和j之间的间隔数(因为间隔数从小到大渐增,所以大的间隔数总能包含小的间隔数)
    // i     j
    // abcdcba.length = L   所以 L = j-i+1; => j = i+L-1;
    for ( L = 2; L <= len; L++) {
        // 从0开始
        for ( i = 0; i <= len - L; i++) {
                j = i + L - 1;
            if(L == 2 && s[i] == s[j]) {
                dp[i][j] = 1;
                result = s.slice(i, i + L);
            }else if(s[i] == s[j] && dp[i + 1][j - 1] == 1) {
                dp[i][j] = 1
                result = s.slice(i, i + L);
            }

        }
    }
    //console.log(result);
    return result;
}

复制代码

方法的时间复杂度为O(n^2), 时间复杂度也为O(n^2), 效率上总体来说相对暴力解法有很大的提升, 是一种不错的解法, 而且动态规划的应用场景很多, 想进一步学习的老铁可以点这里动态规划应用场景。

第三种 Manacher算法

Manacher算法,又叫“马拉车”算法,可以在时间复杂度为O(n)的情况下求解一个字符串的最长回文子串长度的问题。

在进行Manacher算法时,字符串都会进行上面的进入一个字符处理,比如输入的字符为acbbcbds,用“#”字符处理之后的新字符串就是#a#c#b#b#c#b#d#s#。

var str = 'ddabbade'
const longestPalindrome = function (s) {
  if (s.length == 1) {
    return s
  }
  let str = '#' + s.split('').join('#') + '#'
  let rl = []
  let mx = 0
  let pos = 0
  let ml = 0
  for (let i = 0; i < str.length; i++) {
    if (i < mx) {
      rl[i] = Math.min(rl[2 * pos - i], mx - i)
    } else {
      rl[i] = 1
    }
    while (i - rl[i] > 0 && i + rl[i] < str.length && str[i - rl[i]] == str[i + rl[i]]) {
      rl[i]++
    }
    if (rl[i] + i - 1 > mx) {
      mx = rl[i] + i - 1
      pos = i
    }
    if (ml < rl[i]) {
      ml = rl[i]
      sub = str.substring(i - rl[i] + 1, i + rl[i])
    }
  }
  return sub.split('#').join('').trim()
}
console.log(longestPalindrome(str)) //输出dabbad
复制代码

该方法的时间复杂度为O(n),效率相对前两种方法有巨大的提升。有一篇大佬的文章有助于大家对Manacher算法的理解Manacher算法详解

总结

这三种方法是最长回文子串的最常用解法。 暴力解法最容易理解也是最简单,但是算法效率低下。 动态规划对暴力解法做了一定的改进,它避免了在验证回文时进行不必要的重复计算。 而Manacher算法则是此题效率最高的算法,虽然相对前两种方法稍微难理解一点,但是仔细看看也OK啦:smile:。 大家如果还有什么更优的解法,欢迎评论区见:smile: 最后容许小生附上我的 github地址 里面记录了我学习前端的点点滴滴,觉得有帮助的小哥哥小姐姐可以给个小星星哟:smile:


以上所述就是小编给大家介绍的《leetcode解题系列-最长回文子串最全解法》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

计算智能

计算智能

Russell C. Eberhart、Yuhui Shi / 人民邮电出版社 / 2009-2 / 69.00元

《计算智能:从概念到实现(英文版)》面向智能系统学科的前沿领域,系统地讨论了计算智能的理论、技术及其应用,比较全面地反映了计算智能研究和应用的最新进展。书中涵盖了模糊控制、神经网络控制、进化计算以及其他一些技术及应用的内容。《计算智能:从概念到实现(英文版)》提供了大量的实用案例,重点强调实际的应用和计算工具,这些对于计算智能领域的进一步发展是非常有意义的。《计算智能:从概念到实现(英文版)》取材......一起来看看 《计算智能》 这本书的介绍吧!

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具