-
Notifications
You must be signed in to change notification settings - Fork 59
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Find The Longest Palindromic Substring #5
Comments
还是只能用正常的思路实现,抛砖引玉了 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
} |
@chechengpeng 很暴力 😈 |
@barretlee 数据结构和算法了解的不多,只能这么的暴力搞了 |
普通的暴力复杂度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 那个判断回文是从两边往中间比较,感觉万一比较到最后一个不相等... 还看了几个解法,总结如下: 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);
}; |
@Robin-front Manacher 算法需要中点,填间隔符可以让偶数回串当奇数算。前后的 NaN 做哨兵方便判断。 |
占个位先... 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 方法2:从中间判断, 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 方法3:Manacher算法,O(n); 具体的讲解可以参考这篇文章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 '' |
找到字符串 s 中最长的连续回文串,假定 s 的最大长度为 1000,如
参考答案:https://github.com/barretlee/daily-algorithms/blob/master/answers/5.md
The text was updated successfully, but these errors were encountered: