Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd" Output: "bb"
Constraints:
1 <= s.length <= 1000sconsist of only digits and English letters.
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd" 输出："bb"
提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
| Language | Runtime | Memory | Submission Time |
|---|---|---|---|
| javascript | 304 ms | N/A | 2018/11/17 16:15 |
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
if(s === null || s.length <=1 ){
return s ;
}
const len = s.length;
var boolTable = new Array(len);
for (var i = 0; i < len; i++) {
boolTable[i] = new Array(len);
}
for (i=0;i<len;i++) {
boolTable[i][i] = true;
}
for (i=0;i<len-1;i++) {
boolTable[i+1][i] = s.charAt(i)===s.charAt(i+1);
}
for (var j=0;j<len;j++) {
for(i=0;i<j;i++) {
if(j-i>1) {
boolTable[j][i] = boolTable[j-1][i+1] && s.charAt(i) === s.charAt(j);
}
}
}
var ansI = -1,
ansJ = -1,
maxLength = -1;
for (j=0;j<len;j++) {
for (i=0;i<=j;i++) {
if (boolTable[j][i] && j-i>=maxLength) {
ansI = i;
ansJ = j;
maxLength = j-i;
}
}
}
return s.slice(ansI,ansJ+1);
}设dp[i][j] 为以 s 时的子串是否是回文。
递推式为:
暴力法将选出所有子字符串可能的开始和结束位置，并检验它是不是回文。
function reverse(str){
return str.split('').reverse().join('');
};
var longestPalindrome = function(s) {
if (s) {
var len = s.length,
ansArray = [],
max = -1,
maxIndex = -1,
temp = "",
tempReversed = "";
for (var i = 0; i < len; i++) {
for (var j = i; j < len; j++) {
temp = s.slice(i, j+1);
tempReversed = reverse(temp);
if (temp === tempReversed && temp.length >= max) {
ansArray.push(temp);
max = temp.length;
}
}
}
return ansArray[ansArray.length-1];
} else {
return "";
}
};时间复杂度：O(n^3)
常见错误
有些人会忍不住提出一个快速的解决方案，不幸的是，这个解决方案有缺陷(但是可以很容易地纠正)：
反转 SS，使之变成 S'S′。找到 SS 和 S'S′ 之间最长的公共子串，这也必然是最长的回文子串。
这似乎是可行的，让我们看看下面的一些例子。
例如，S=“caba” , S′=“abac”：
S 以及 S‘ 之间的最长公共子串为 “aba”，恰恰是答案。
让我们尝试一下这个例子：S = “abacdfgdcaba“ , S′=“abacdgfdcaba”：
S 以及 S′ 之间的最长公共子串为 “abacd”，显然，这不是回文。
算法
我们可以看到，当 SS 的其他部分中存在非回文子串的反向副本时，最长公共子串法就会失败。为了纠正这一点，每当我们找到最长的公共子串的候选项时，都需要检查子串的索引是否与反向子串的原始索引相同。如果相同，那么我们尝试更新目前为止找到的最长回文子串；如果不是，我们就跳过这个候选项并继续寻找下一个候选。
function reverse(str){
return str.split('').reverse().join('');
};
var longestPalindrome = function(s) {
if (s) {
var commonString = [],
sReversed = reverse(s),
len = s.length,
max = -1,
maxIndex = -1,
temp = "";
for (var i = 0; i < len; i++) {
for (var j = i; j < len; j++) {
temp = s.slice(i, j+1);
if(sReversed.indexOf(temp) >= 0 && sReversed.indexOf(temp) === len-j-1 && temp.length >= max) {
commonString.push(temp);
max = temp.length;
}
}
}
return commonString[commonString.length-1];
} else {
return "";
}
};时间按复杂度：O(n^2)
为了改进暴力法，我们首先观察如何避免在验证回文时进行不必要的重复计算。考虑 “ababa” 这个示例。如果我们已经知道 “bab” 是回文，那么很明显，“ababa” 一定是回文，因为它的左首字母和右尾字母是相同的。
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
if(s === null || s.length <=1 ){
return s ;
}
const len = s.length;
var boolTable = new Array(len);
for (var i = 0; i < len; i++) {
boolTable[i] = new Array(len);
}
for (i=0;i<len;i++) {
boolTable[i][i] = true;
}
for (i=0;i<len-1;i++) {
boolTable[i+1][i] = s.charAt(i)===s.charAt(i+1);
}
for (var j=0;j<len;j++) {
for(i=0;i<j;i++) {
if(j-i>1) {
boolTable[j][i] = boolTable[j-1][i+1] && s.charAt(i) === s.charAt(j);
}
}
}
var ansI = -1,
ansJ = -1,
maxLength = -1;
for (j=0;j<len;j++) {
for (i=0;i<=j;i++) {
if (boolTable[j][i] && j-i>=maxLength) {
ansI = i;
ansJ = j;
maxLength = j-i;
}
}
}
return s.slice(ansI,ansJ+1);
}时间复杂度：O(n^2)