題目描述
給定一個(gè)字符串 s换帜，找到 s 中最長(zhǎng)的回文子串楔壤。你可以假設(shè) s 的最大長(zhǎng)度為 1000。
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個(gè)有效答案惯驼。
示例 2：
輸入: "cbbd"
輸出: "bb"
解法
方法一
暴力破解法蹲嚣，時(shí)間復(fù)雜為O(n^3)递瑰。
var longestPalindrome = function(s) {
let max_len = 0;
let max_str = '';
const len = s.length;
if (s == undefined || len === 1) return s;
for (let i = 0; i < len; i++) {
let max_len_of_current_str = 0;
for (let j = 1; j <= len - i; j++) {
const current_str = s.substr(i, j);
const is_palindrome = check_is_palindrome(current_str);
if (is_palindrome && j > max_len_of_current_str) {
max_len_of_current_str = j;
}
}
if (max_len < max_len_of_current_str) {
max_len = max_len_of_current_str;
max_str = s.substr(i, max_len_of_current_str);
}
}
return max_str;
};
const check_is_palindrome = (s) => {
const len = s.length;
if (s == undefined || len < 1) return false;
let front = 0;
let back = len -1;
while (front < back) {
if (s[front] !== s[back]) {
return false;
}
front++;
back--;
}
return true;
};
