algorithmbook
algorithmbook copied to clipboard
回文专题
5. Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1: Input: "babad" Output: "bab"
Example 2: Input: "cbbd" Output: "bb"
中心扩展法
1.思想:
1)将子串分为单核和双核的情况,单核即指子串长度为奇数,双核则为偶数;
2)遍历每个除最后一个位置的字符index(字符位置),单核:初始low = 初始high = index,low和high均不超过原字符串的下限和上限;判断low和high处的字符是否相等,相等则low++、high++(双核:初始high = 初始low+1 = index + 1);
3)每次low与high处的字符相等时,都将当前最长的回文子串长度与high-low+1比较。后者大时,将最长的回文子串改为low与high之间的;
4)重复执行2)、3),直至high-low+1 等于原字符串长度或者遍历到最后一个字符,取当前截取到的回文子串,该子串即为最长的回文子串。
2.时间复杂度解释:
遍历字符:一层循环、O(n-1);
找以当前字符为中心的最长回文子串:嵌套两个独立循环、O(2n*(n-1)) = O(n^2)。
function longestPalindrome( s) {
if(s.length <= 1)
return s;
var carry = { sub: '', maxLen: 0}
var n = s.length - 1; //因为i+1, 需要多留一个
for(var i = 0;i < n;i++){
findLongestPalindrome(s,i,i,n, carry);//单核回文
findLongestPalindrome(s,i,i+1,n, carry);//双核回文
}
return carry.sub;
}
function findLongestPalindrome( s, low, high, n, carry ){
while (low >= 0 && high <= n){
if(s[low] == s[high]){
if(high - low + 1 > carry.maxLen){
carry.maxLen = high - low + 1;
carry.sub = s.substring(low , high+1);
}
low --;//向两边扩散找当前字符为中心的最大回文子串
high ++;
} else{
break;
}
}
}
更简单的表现形式
function centerExtend(left, right, str) {//单核回文文
var sub = str[left]
while (true) {
var b = str[left];
var c = str[right];
if (!b || !c) {
break
}
if (b === c) {
sub = str.substring(left, right + 1)
left--
right++
} else {
break
}
}
return {
len: sub.length,
sub
}
}
function resolve(str) {
var max = -1
var maxSub = ''
for (var i = 0; i < str.length; i++) {
var a = centerExtend(i, i, str);
if (a.len >= max) {
max = a.len;
maxSub = a.sub;
}
var b = centerExtend(i, i + 1, str);
if (b.len >= max) {
max = b.len;
maxSub = b.sub
}
}
console.log(maxSub)
return maxSub
}
resolve("ABBABB")
马拉车算法,最好的解释 https://www.cnblogs.com/bitzhuwei/p/Longest-Palindromic-Substring-Part-II.html