算法练习

leetcode

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

示例：

输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。

输入: “cbbd” 输出: “bb”

思路分析

1.暴力搜索

最简单的办法是找出字符串中的所有子串，判断其是否为回文串，然后记录下其中最大的回文子串即可。

暴搜无例外的话效率都很低，这个算法是 O(N^3) 的。首先找出所有子串 是 O(N^2) 的，然后判断其是否为回文是 O(N) 的。

解法如下:


function longestPalindrome(s){
    let tempStr = "";
    let longestStr = "";
    for(let i = 0;i < s.length;i++) {
        tempStr = ""
        for(let j = i;j < s.length;j++) {
          tempStr += s.charAt(j)
        }
        if(isPalindrome(tempStr) && tempStr.length > longestStr.length) {
          longestStr = tempStr;
        }
    }
    return  LongestStr;

    function  isPalindrome(s) {
      let rev = s.split('').reverse().join('')
      return rev === s
    }
}

2.动态规划

DP可能是解这个问题的一个好方法，然而算法复杂度依然是 O(N^2) 的，而且空间复杂度也是 O(N^2)。

我们假设用 P[i][j] 来表示 s[i..j] 是否是一个回文子串。

它的计算公式长这样：

P[i][j] = s[i] === s[j] && P[i + 1][j - 1] ? true : false;

这产生了一个直观的动态规划解法，我们首先初始化一字母和二字母的回文，然后找到所有三字母回文，并依此类推…


let longestPalindrome_dp = function(s) {
  let i,j,len;

  //isPalindrom[i][j] represent s[i..j] is a parlindrom string or not.

  let isPalindrom = new Array(s.length);
  for(let i = 0;i < s.length;i++) {
    isPalindrom[i] = new Array(s.length).fill(false);
  }
}
赞 赏