daily-algorithms
daily-algorithms copied to clipboard
Published
20 hours ago •
barretlee
barretlee
Find The Longest Palindromic Substring
本题难度：★★
找到字符串 s 中最长的连续回文串，假定 s 的最大长度为 1000，如
输入 "babad"，输出 "bab"，"aba" 也是正确答案
输入 "cbbd"，输出 "bb"
参考答案：https://github.com/barretlee/daily-algorithms/blob/master/answers/5.md
还是只能用正常的思路实现，抛砖引玉了
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
}
普通的暴力复杂度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();
}
马上去学习了 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('')
}
@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);
};
占个位先... 问题：找到字符串 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 ''
