Find The Longest Palindromic Substring

[barretlee]

本题难度：★★

找到字符串 s 中最长的连续回文串，假定 s 的最大长度为 1000，如

输入 "babad"，输出 "bab"，"aba" 也是正确答案
输入 "cbbd"，输出 "bb"

参考答案：https://github.com/barretlee/daily-algorithms/blob/master/answers/5.md

[chechengpeng]

还是只能用正常的思路实现，抛砖引玉了

function findPal(str) {
  var len = str.length;
  for(let i=0;i<len;i++){
    for(let j=0;j<=i;j++){
      var str2 = str.substr(j,len-i)
      if(isPal(str2)){
        return str2;
      }
    }
  }
}

function isPal(str) {
  return str.split('').reverse().join('') === str
}

[barretlee]

@chechengpeng 很暴力 😈

[chechengpeng]

@barretlee 数据结构和算法了解的不多，只能这么的暴力搞了

[codingdie]

普通的暴力复杂度n^3 ,动态规划n*n ,马拉车算法n。3个月前刷leetcode的代码:

public String longestPalindrome(String s) {
    if (s.isEmpty()) return "";
    if (s.length() == 1) return s;
    StringBuffer stringBuffer = new StringBuffer();
    stringBuffer.append("#");
    for (char ch : s.toCharArray()) {
        stringBuffer.append(ch).append("#");
    }
    s = stringBuffer.toString();
    int length = s.length();
    int[] table = new int[length];
    int maxRight = 0, pos = 0, max = 1, maxpos = 0;
    char maxCh = '#';
    for (int i = 0; i < length && maxRight < length - 1; i++) {
        int j = 2 * pos - i;
        if (i < maxRight) {
            if (table[j] < maxRight - i) {
                table[i] = table[j];
            } else {
                int k = maxRight - i;
                int m = i - (k), n = i + (k);
                while (--m >= 0 && ++n < length && s.charAt(m) == s.charAt(n)) {
                    k++;
                }
                table[i] = k;
                maxRight = i + k - 1;
                pos = i;
                if (k > max || (k == max && s.charAt(i) != '#' && maxCh == '#')) {
                    max = k;
                    maxpos = i;
                    maxCh = s.charAt(i);
                }
            }
        } else {
            int m = i, n = i;
            int k = 1;
            while (--m >= 0 && ++n < length && s.charAt(m) == s.charAt(n)) {
                k++;
            }
            table[i] = k;
            maxRight = i + k - 1;
            pos = i;
            if (k > max || (k == max && s.charAt(i) != '#' && maxCh == '#')) {
                max = k;
                maxpos = i;
                maxCh = s.charAt(i);
            }
        }

    }
    StringBuffer resultBuffer = new StringBuffer();
    for (int i = maxpos - max + 1; i < maxpos + max; i++) {
        char charAt = stringBuffer.charAt(i);
        if (charAt != '#') {
            resultBuffer.append(charAt);
        }
    }
    return resultBuffer.toString();
}

[crimx]

马上去学习了 Manacher 算法，比较了一番这个讲得最清晰易懂 。Manacher 马拉车算法。

function manacher (str) {
  str = String(str)

  var arr = [NaN, null]
  for (let i = 0; i < str.length; i += 1) {
    arr.push(str[i])
    arr.push(null)
  }
  arr.push(NaN)

  var iCenterMax = 1
  var lens = []
  var iCenter = 0
  var iRight = 0
  for (let i = 1; i < arr.length - 1; i += 1) {
    if (arr.length - 1 - i <= lens[iCenterMax]) {
      break
    }

    lens[i] = 0

    if (i < iRight) {
      let iMirror = 2 * iCenter - i
      lens[i] = Math.min(iRight - i, lens[iMirror])
    }

    while (arr[i + lens[i] + 1] === arr[i - lens[i] - 1]) {
      lens[i] += 1
    }

    if (i + lens[i] > iRight) {
      iCenter = i
      iRight = i + lens[i]
    }

    if (lens[i] > lens[iCenterMax]) {
      iCenterMax = i
    }
  }

  return arr.slice(iCenterMax - lens[iCenterMax], iCenterMax + lens[iCenterMax] + 1)
    .filter(item => item !== null)
    .join('')
}

[Robin-front]

@huirong 那个判断回文是从两边往中间比较，感觉万一比较到最后一个不相等...
@crimx 判断回文是中间往两边比较，但是好像加了一堆null, NaN是为了正确计算回文字符串长度？

还看了几个解法，总结如下：

var longestPalindrome = function(s) {
    var len = s.length,  max = 1,  start = 0,  temp = 0;
    if (len <= 1){ return s;}
    for (var i=0; i < len; i++){
        if ((len-i) <= max/2){ // 如果剩余长度不足max一半，那就不用再找了。
            break;
        }
        var left = i, right = i; //从当前指针向两边找
        while(right < len-1 && s[right] === s[right+1]){ // 连续相同字符，不管奇偶，都是回文，直接跳过
            right++;
        }
        i = right; // 跳过相同字符，加速遍历
        while(right<len-1 && left>0 && s[right+1] === s[left-1]){ // 满足回文条件
            right++; left--;
      	}
        temp = right-left+1;
        if (temp > max){
            max = temp;
            start = left;
        }

    }
    return s.substr(start, max);
};

[crimx]

@Robin-front Manacher 算法需要中点，填间隔符可以让偶数回串当奇数算。前后的 NaN 做哨兵方便判断。

[YabZhang]

占个位先...
问题：找到字符串 s 中最长的连续回文串。
方法１：从两端判断回文序列，O(n^3)

def check_palindrome(seq, start, end):
    length = 0
    while(start <= end):
        if seq[start] == seq[end]:
            start += 1
            end -= 1
            length += 2
        else:
            return 0
    # fixup length when length of seq is odd
    if abs(end - start) % 2 == 0:
        length -= 1
    return length

def resolve_v1(seq):
    result = ''
    max_len = 0
    for i in range(len(seq)):
        for j in range(len(seq) - 1, i, -1):
            t_len = check_palindrome(seq, i, j):
            if t_len > max_len:
                max_len = t_len
                result = seq[i: j + 1]
    return result

方法２：从中间判断， O(n^2)

def check_palindrome_from_center(seq, first, second):
    result = ''
    max_n = 0
    while(first >= 0 and second < len(seq)):
        if seq[first] == seq[second]:
            first -= 1
            second += 1
            max_n += 1
        else:
            break
    return max_n

def resolve_v2(seq):
    result = ''
    max_n = 0
    for i in range(len(seq)):
        # odd
        odd_tn = check_palindrome_from_center(seq, i, i)
        if (odd_tn * 2 - 1) > max_n:
            max_n = odd_tn * 2 -1
            result = seq[(i - odd_tn + 1): (i + odd_tn)]
        # even
        even_tn = check_palindrome_from_center(seq, i, i + 1)
        if even_tn * 2 > max_n:
            max_n = even_tn * 2
            result = seq[(i - even_tn + 1): (i + even_tn + 1)]
    return result

方法３：Manacher算法，O(n)；
在上述的第二种情况中，需要区分回文序列的长度分别为奇偶的情况；
manacher算法对待处理的序列进行了预处理O(n)，然后对预处理后的串只需要考虑奇数情况即可。
插入的预处理效果类似于：　123 => 12*3，即把原有序列元素的前后都插入一个占位元素;
这个算法之所以高效的原理在于较少了冗余计算，尽可能提高每一步计算结果的可复用性。

具体的讲解可以参考这篇文章https://www.felix021.com/blog/read.php?2040

下面给出代码实现：

def resolve_v3(seq):
    new_seq = '#%s#' % '#'.join(list(seq))
    new_arr = [1] * len(new_seq)
    
    dx = 0
    rt_most = 0
    for idx, e in enumerate(new_seq):
        if idx < rt_ most:
            new_arr[idx] = min(new_arr[2 * dx - idx], rt_most - i + 1)
        n = new_arr[idx]

        while(idx - n >= 0 and idx + n < len(new_seq)):
            if (new_arr[idx + n] == new_arr[idx - n]):
                n += 1
            else:
                break
        new_arr[idx] = n

        if idx + new_arr[idx] > rt_most:
            dx = idx
            rt_most = new_arr[idx] + idx - i
        
    max_n = max(new_arr)
    for i in range(len(new_arr)):
        if new_arr[i] == max_n:
            p = max_n - 1
            return ''.join(wd for wd in new_seq[i - p: i + p + 1] if wd != '#')
    return ''