LeetCode 5. Longest Palindromic Substring 最长回文子串 JS

末蓝、 2024-04-17 06:26 55阅读 0赞

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

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

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

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

/**
     * @param {string} s
     * @return {string}
     */
    var longestPalindrome = function(s) {
        
        let result = '';
        for(let i = 0;i<s.length;i++){
        
            for(let j=i+1;j<=s.length;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;
    };

**中心扩展法**  
step 1:遍历每个字符,把每个字符当做中心逐步向两边扩展,每扩展一步就得到一个新的子串。这里针对输入字符串的长度，扩展方式需要根据长度奇偶性质做判断；  
Step 2:判断子串是否为回文串，更新当前最长回文串；  
Step 3:返回最长回文串。

时间复杂度：  
遍历字符串的时间复杂度为O(n),中心扩展及判断子串是否为回文串的时间复杂度为O(n),二者相乘得到动态规划法的时间复杂度为O(n^2)。

空间复杂度:  
该方法没有使用额外的空间，空间复杂度为O(n)。

/**
     * @param {string} s
     * @return {string}
     */
    var longestPalindrome = function (s) {
        
      let maxLen = 0;
      let start = 0;
      //长度为奇数
      for (let i = 0; i < s.length; i++) {
        
        let j = i - 1;
        let k = i + 1;
        while (j >= 0 && k < s.length && s.charAt(j) === s.charAt(k)) {
        
          if (k - j + 1 > maxLen) {
        
            maxLen = k - j + 1;
            start = j;
          }
          j -= 1;
          k += 1;
        }
      }
      //长度为偶数
      for (let i = 0; i < s.length; i++) {
        
        let j = i;
        let k = i + 1;
        while (j >= 0 && k < s.length && s.charAt(j) === s.charAt(k)) {
        
          if (k - j + 1 > maxLen) {
        
            maxLen = k - j + 1;
            start = j;
          }
          j -= 1;
          k += 1;
        }
      }
      if (maxLen > 0) {
        
        return s.slice(start, start + maxLen);
      } else{
        
        return s.slice(0,1);
      }
    };

**Manacher算法**  
作用：线性时间解决最长回文子串问题。  
思想：Manacher充分利用了回文的性质，从而达到线性时间。  
首先先加一个小优化，就是在每两个字符（包括头尾）之间加没出现的字符（如\#），这样所有字符串长度就都是奇数了，方便了很多。  
记录p\[i\]表示i能向两边推（包括i）的最大距离，如果能求出p，则答案就是max§-1了（以i为中点的最长回文为2\*p\[i\]-1，但这是加过字符后的答案，把加进去的字符干掉，最长回文就是p\[i\]-1）。

我们假设p\[1~i-1\]已经求好了，现在要求p\[i\]：  
假设当前能达到的最右边为R，对应的中点为pos，j是i的对称点。  
1.当i＜R时  
![在这里插入图片描述][20190903102205425.png]  
由于L~R是回文，所以p\[i\]=p\[j\]（i的最长回文和j的最长回文相同）。  
![在这里插入图片描述][20190903102230732.png]  
这种情况是另一种：j的最长回文跳出L了。那么i的最长回文就不一定是j的最长回文了，但蓝色的肯定还是满足的。

综上所述，p\[i\]=min(p\[2\*pos-i\],R-i)。  
2.当i>=R时  
由于后面是未知的，于是只能暴力处理了。  
效率：但是这样看起来很暴力，为什么复杂度是O(len)的呢？因为R不会减小，每次暴力处理的时候，p\[i\]增大多少，就说明R增大多少，而R最多增加len次。所以复杂度是O(len)的。

/**
     * @param {string} s
     * @return {string}
     */
    var 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()
    };

参考链接：https://blog.csdn.net/zzkksunboy/article/details/72600679 CSDN博主「ZigZagK」的原创文章，遵循 CC 4.0 BY-SA 版权协议

[20190903102205425.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/8b16ffa480814263bea0ade8b42121d5.png
[20190903102230732.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/55c73173dc7849b68d6ff42278460a15.png