leetcode 5题 最长的回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
示例1
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例2
输入：s = "cbbd"
输出："bb"
思路
动态规划
代码
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
if(!s || s.length < 2){
return s;
}
var s_f = s.split('').reverse().join('');
var resultStr = s[0];
var maxLen = 1;
var tmpLen = 1;
var maxStrIndex = 0;
var len = s.length;
//判断字符串是否回文
function isPalinerome(i,r){
if(len - i - 1 == r -tmpLen + 1){
return true
}
return false;
}
//初始化二维数组
var len = s.length;
var arr = new Array(len);
for(var i = 0;i<len;i++){
arr[i] = [];
for(var r = 0;r<len;r++){
arr[i][r] = 0
}
}
for(var i = 0;i<len;i++){
for(var r=0;r<len;r++){
if(s[i] == s_f[r]){
if(i==0 || r==0){
arr[i][r] = 1
}else{
arr[i][r] = arr[i-1][r-1] + 1
tmpLen = arr[i][r]
}
if(tmpLen > maxLen && isPalinerome(i,r)){
maxStrIndex = r;
maxLen = tmpLen;
resultStr = s.substring(i-tmpLen+1,i+1);
}
}
}
}
return resultStr;
};
复杂度分析:
- 时间复杂度: O(N^2)
- 空间复杂度：O(N^2)