时间戳

首页 > 解决方案 > Javascript中最长的回文子串

javascript - Javascript中最长的回文子串

问题描述

我正在尝试以 O(N^2) 时间复杂度解决最长回文子串问题。

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

示例 1：

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

示例 2：

Input: "cbbd"
Output: "bb"

我的解决方案：

var longestPalindrome = function(s) {
    if(!s || s.length === 0)    return "";
    
    let start = 0;
    let end = 0;
    
    for(let i=0; i<s.length; i++) {
        let len1 = expand(s, i, i);
        let len2 = expand(s, i, i+1);
        let size = Math.max(len1, len2);
        if(size > end-start) {
            start = Math.floor(i - ((size-1) / 2));
            end = Math.floor(i + (size/2));
        }
    }
    
    return s.substring(start, end+1);
};

const expand = (str, left, right) => {
    let l = left;
    let r = right;
    while(l >= 0 && r < str.length && str[l] === str[r]) {
        l--;
        r++;
    }
    
    return r-l-1;
}

我的解决方案适用于示例 1，但不适用于示例 2。它返回“cbb”而不是“bb”。有谁知道我做错了什么？

谢谢

标签： javascriptstringtime-complexity

解决方案

很简单，替换

start = Math.floor(i - ((size-1) / 2));

和

start = i - Math.floor((size-1) / 2);

如前所述，您的复杂性将是O(n^2). 如果你在乎，有可能得到O(n log(n))，但这种技术要困难得多。它涉及以这样一种方式对语料库（输入字符串）进行散列处理，以便您可以O(1)使用O(n)precomp 获取子字符串散列，然后对于每个起始字符（或一对相邻的相似字符）二进制搜索到该索引处的 LPS（所以你'也需要反向哈希）。我相信您可以在互联网上的某个地方找到更好的解释。GL！

推荐阅读