leetcode Problem 5 最长子回文串
leetcode Problem 5 最长子回文串
flytam
发布于 2020-01-14 16:55:21
发布于 2020-01-14 16:55:21
题目：Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
1、暴力做法。 遍历所有的子串，求出最长。复杂度O(n3)。显然GG了。 2、动态规划 把一个大问题分解成每一个小问题进行求解。假设字符串s，则s[i]到s[j]是回文的话，s[i+1]到s[j-1]也是回文；或者说，已知s[i+1]到s[j-1]是回文的情况下，如果s[i]==s[j]则，s[i]到s[j]就是回文，我们用数组table[i][j]来表示i到j的是否回文状态。代码如下，复杂度是o(n2)。
var longestPalindrome = function (s) {
const length = s.length;
let table = [];
for (let i = 0; i < 1000; i++) {
table[i] = new Array();
for (let j = 0; j < 1000; j++) {
table[i][j] = 0;
}
}
let maxlength = 1,
maxstr,
longestbegin;
for (let i = 0; i < length; i++) {
table[i][i] = 1; //所有的 i 到 i的字符串是回文
longestbegin = i;
}
for (let i = 0; i < length - 1; i++) {
//长度为2的回文
if (s[i] === s[i + 1]){
table[i][i + 1] = 1;
maxlength = 2;
longestbegin = i;
}
}
//状态转移 再table[i+1][j-1] == 1的情况下，如果i === j，则 table[i][j]为1 从长度为3的回文开始
for (let len = 3; len <= length; len++) {
for (let i = 0; i < length - len + 1; i++) {
//遍历所有长度为len的字符串
let j = i + len - 1;//两种情况 单数回文和双数回文
//let j = len % 2 === 0?i + len - 2
if (s[i] === s[j] && table[i + 1][j - 1] === 1) {
table[i][j] = 1;
maxlength = len;
longestbegin = i;
}
}
}
//console.log(longestbegin, maxlength)
return s.slice(longestbegin,longestbegin + maxlength)
};然而，这里还是过不了leetcode的。显然，还需要优化的地方 好像o(n2)也是能强行过的。。把字符串换成数组再处理。不过时间只优于百分之1的人，太菜了23333
//最长回文串 o(n2)
var longestPalindrome = function (s) {
const length = s.length;
s = s.split('');
let table = [];
let maxlength = 1,
maxstr,
longestbegin = 0;
for (let i = 0; i < length; i++) {
table[i] = new Array();
table[i][i] = 1;
}
for (let i = 0; i < length - 1; i++) {
//长度为2的回文
if (s[i] === s[i + 1]) {
table[i][i + 1] = 1;
maxlength = 2;
longestbegin = i;
}
}
//状态转移 再table[i+1][j-1] == 1的情况下，如果i === j，则 table[i][j]为1 从长度为3的回文开始
for (let len = 2; len <= length; len++) {
for (let i = 0; i < length - len + 1; i++) {
//遍历所有长度为len的字符串
let j = i + len - 1; //两种情况 单数回文和双数回文
//let j = len % 2 === 0?i + len - 2
if (s[i] === s[j] && table[i + 1][j - 1] === 1) {
table[i][j] = 1;
maxlength = len;
longestbegin = i;
}
}
}
//console.log(longestbegin, maxlength)
return s.join('').slice(longestbegin, longestbegin + maxlength)//真的是日了狗。。。数组处理比字符串处理要快
};
这里写图片描述
而且不是每次都能过，这个还是要优化的啊
换另一种思路，就是。遍历字符串中的每个字符。算出以该字符为中心的最长回文串
var longestPalindrome2 = function (s) {
function expandAroundCenter(s, l, r) {
while (l >= 0 && r < sLen && s[l] == s[r]) {
l--;
r++;
}
return r - l - 1;
}
let start = 0,
end = 0,
len1 = 0,
len2 = 0,
len = 0,
sLen = s.length;
for (let i = 0; i < sLen; i++) {
len1 = expandAroundCenter(s, i, i);//aba这种回文
len2 = expandAroundCenter(s, i, i + 1);//abba这种回文
len = Math.max(len1, len2);//算出较大的回文
if (len > end - start) {
end = i + (len >> 1);
start = end + 1 - len;
}
}
return s.substring(start, end + 1);
};这次就快多了。。。。
这里写图片描述
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读