leetcode-5. 最长回文子串。
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2:
输入: "cbbd"
输出: "bb"
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problemset/all/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
char *longestPalindrome( char *s ) {
char *answer = NULL, tempS[2002] = "#";
int i = 0, j = 0, count[2] = {0};
answer = malloc( sizeof(char *) * 1000 );
for( j = 1, i = 0; s[i] != ' '; ++i ) {
tempS[j++] = s[i];
tempS[j++] = '#'; // 在每个字符后面都加上'#'.
}
for( i = 0; tempS[i] != ' '; ++i ) {
// 探测以i为中心向两边扩展的最大偏移量.
for( j = 1; i - j >= 0 && tempS[i + j] != ' ' && tempS[i - j] == tempS[i + j]; ++j ) {}
if( j - 1 > count[0] ) {
count[0] = j - 1; // 以i为中心向两边扩展的偏移量, 不包括中心点.
count[1] = i - (j - 1); // 以i为中心的左边界.
}
}
for( i = count[1], j = 0; j < count[0]; ++i ) {
char ch = tempS[i];
if( ch != '#' ) {
answer[j++] = ch;
}
}
answer[j] = ' ';
return answer;
}
char *longestPalindrome( char *s ) {
char *answer = NULL;
int *dp = NULL, slen = strlen( s );
int i = 0, j = 0, sub = 0, start = 0, max = 1;
if( slen < 2 ) {
return s;
}
answer = malloc( sizeof(*answer) * (slen + 1) );
dp = malloc( sizeof(*dp) * slen * slen );
for( sub = 1; sub <= slen; ++sub ) { // sub表示子串长度.
for( i = 0; i + sub - 1 < slen; ++i ) { // 以i位置为起点.
j = i + sub - 1; // 以j位置为终点.
if( sub == 1 ) {
dp[i * slen + j] = 1;
} else if( sub == 2 ) {
dp[i * slen + j] = s[i] == s[j];
} else {
dp[i * slen + j] = s[i] == s[j] && dp[(i + 1) * slen + (j - 1)];
}
if( dp[i * slen + j] ) {
start = i;
max = sub;
}
}
}
free( dp );
for( i = 0; i < max; ++i ) {
answer[i] = s[start + i];
}
answer[i] = ' ';
return answer;
}
char *longestPalindrome( char *s ) {
char *answer = NULL, *ta = NULL, ch = '#';
int i = 0, j = 0, slen = strlen( s );
int *radius = NULL; // 回文半径数组.
int right = -1; // 出现过的回文最右边界.
int center = -1; // 第一次出现回文最右边界时的回文中心.
int left = -1; // 以 center 为回文中心的回文左边界.
int mirror = -1; // i 以 center 为中心的镜像 i'.
int mirrorLeft = -1; // 以 i' 为回文中心的回文左边界.
int mRadius = -1, mCenter = -1;
answer = malloc( sizeof(*answer) * (slen + 1) );
ta = malloc( sizeof(*ta) * (slen * 2 + 2) );
for( ta[j++] = ch; (ta[j++] = s[i++]) != ' '; ta[j++] = ch ) {}
radius = malloc( sizeof(*radius) * (slen * 2 + 1) );
for( i = 0; ta[i] != ' '; ++i ) {
if( i > right ) {
// i位置在回文最右边界外, 暴力扩.
for( j = 1; i - j >= 0 && ta[i - j] == ta[i + j]; ++j ) {}
radius[i] = j - 1;
} else {
left = center - radius[center]; // 以 center 为回文中心的回文左边界.
mirror = center * 2 - i; // i 以 center 为中心的镜像 i'.
mirrorLeft = mirror - radius[mirror]; // 以 i' 为回文中心的回文左边界.
// i位置在回文最右边界内,根据 i' 的回文左边界又可分为3种情况.
if( mirrorLeft < left ) {
radius[i] = right - i;
} else if( mirrorLeft == left ) {
for( j = right - i + 1; i - j >= 0 && ta[i - j] == ta[i + j]; ++j ) {}
radius[i] = j - 1;
} else {
radius[i] = radius[mirror];
}
}
if( i + radius[i] > right ) { // 出现较右的回文右边界.
center = i;
right = i + radius[i];
}
if( radius[i] > mRadius ) { // 出现较大的回文半径.
mCenter = i;
mRadius = radius[i];
}
}
free( radius );
i = mCenter - mRadius; // 最长回文的左边界.
j = mCenter + mRadius; // 最长回文的右边界.
for( right = 0; i <= j; ++i ) {
if( ta[i] != ch ) {
answer[right++] = ta[i];
}
}
answer[right] = ' ';
free( ta );
return answer;
}