本题难度：★★ 找到字符串 s 中最长的连续回文串，假定 s 的最大长度为 100

普通的暴力复杂度n^3 ,动态规划n*n ,马拉车算法n。3个月前刷leetcode的代码: <div class="highlight highlight-sou

马上去学习了 Manacher 算法，比较了一番<a href="https://www.youtube.com/watch?v=nbTSfrEfo6M" rel="nof

<a class="user-mention notranslate" data-hovercard-type="user" data-hovercard-url="/us

还是只能用正常的思路实现，抛砖引玉了 <div class="highlight highlight-source-js notranslate position-

<a class="user-mention notranslate" data-hovercard-type="user" data-hovercard-url="/us

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

Find The Longest Palindromic Substring about daily-algorithms HOT 8 OPEN

barretlee commented on May 20, 2024

Find The Longest Palindromic Substring

from daily-algorithms.

Comments (8)

codingdie commented on May 20, 2024 2

普通的暴力复杂度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();
}

from daily-algorithms.

crimx commented on May 20, 2024 1

马上去学习了 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('')
}

from daily-algorithms.

Robin-front commented on May 20, 2024 1

@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);
};

from daily-algorithms.

chechengpeng commented on May 20, 2024

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

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
}

from daily-algorithms.

barretlee commented on May 20, 2024

@chechengpeng 很暴力 😈

from daily-algorithms.

chechengpeng commented on May 20, 2024

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

from daily-algorithms.

crimx commented on May 20, 2024

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

from daily-algorithms.

YabZhang commented on May 20, 2024

占个位先...
问题：找到字符串 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 ''

from daily-algorithms.

Find The Longest Palindromic Substring about daily-algorithms HOT 8 OPEN

Comments (8)

Related Issues (16)

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent