從中間開始向兩端查找
時(shí)間復(fù)雜度，空間復(fù)雜度
- Runtime: 84 ms, faster than 96.85%
- Memory Usage: 37.7 MB, less than 81.26%
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
let start = 0;
let max = 0;
const len = s.length;
for (let i = 0; i < len; i++) {
let len1 = expandRoundCenter(s, i, i, len);
let len2 = expandRoundCenter(s, i, i + 1, len);
const cur = Math.max(len1, len2);
if (cur > max) {
start = i - Math.floor((cur - 1) / 2);
max = cur;
}
}
return s.substr(start, max);
};
var expandRoundCenter = function(s, L, R, len) {
while(L >= 0 && R < len && s[L] === s[R]) {
L--;
R++;
}
return R - L - 1;
}
動(dòng)態(tài)規(guī)劃
- Runtime: 580 ms, faster than 20.63%
- Memory Usage: 71 MB, less than 5.75%
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
let len = s.length
let arr = new Array(len).fill(0).map(item => Array(len).fill(0))
let res = ''
let max = 0
for(let i = 0; i < len; i++) {
for(let j = 0; j <= i; j++) {
if(s[i] === s[j] && (i - j < 3 || arr[j + 1][i - 1] === 1)) {
// 考慮頭尾去掉以后沒有字符剩余，或者剩下一個(gè)字符串的時(shí)候，肯定是回文串
arr[j][i] = 1
let temp = i - j + 1
if (temp > max) {
max = temp
res = s.substr(j, max)
}
}
}
}
return res
};
遞推關(guān)系雖簡單爽待，但真的超級(jí)慢
- Runtime: 1812 ms, faster than 6.94%
- Memory Usage: 69.5 MB, less than 5.38%
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
let n = s.length
let dp = Array(n).fill().map(item => [])
let res = ''
for(let l = 0; l < n; l++) {
for(let i = 0; i + l < n; i++) {
let j = l + i
if(l === 0) {
dp[i][j] = true
} else if (l === 1) {
dp[i][j] = (s[i] === s[j])
} else {
dp[i][j] = (s[i] === s[j]) && dp[i + 1][j - 1]
}
if(dp[i][j] && l + 1 > res.length) {
res = s.substr(i, l + 1)
}
}
}
return res
};
