上一题：LeetCode第4题:findMedianSortedArrays(C语言）
写在前面，最长公共字符串是面试中较常出现的题目，原因是这道题解法众多，可对面试者进行综合考察。
1、暴力求解
思路：双层遍历输入字符串，从而穷举出输入字符串的所有子串，然后再用一层循环，判断子串是否为回文字符串，思路清晰简单，代码略。
2、动态规划
思路：
假设字符串s的长度为length，建立一个length*length的矩阵dp。
dp[i][j]表示“以s[i]开始s[j]结尾的回文串的长度。如果这个字符串不是回文串，让dp[i][j]=0”。显然，j>=i，只需往dp填j>=i的部分即可。
dp[i][j]的递推公式可以这么表述：
（1）首先对dp的对角线元素初始化为1，也就是当i==j时，dp[i][j]=1。
这很显然，每个单独的字符其实就是个长度为1的回文串。
（2）当j-i==1：
若s[i]==s[j]，则dp[i][j]=2；否则dp[i][j]=0。
解释：当j-i==1时，若s[i]==s[j]，则s[i]和s[j]可以组成一个长度为2的回文串。若s[i]！=s[j]，显然他们不可能组成回文串，dp[i][j]=0。
（3）当j-i>=2：
若s[i]==s[j]：若dp[i+1][j-1]>0，则dp[i][j]= dp[i + 1][j - 1] + 2;否则dp[i][j]= 0;
若s[i]！=s[j]：dp[i][j]=0。
解释：如果s[i]==s[j]，表明这个子串有可能是回文串。当去头去尾后它是回文串时，就可以在去头去尾的那个回文串长度基础上+2，得到它的长度。如果去头去尾后不是回文串，那这个子串一定不是回文串，回文串长度只能是0。
若s[i]！=s[j]，显然他们不可能组成回文串，dp[i][j]=0。
只需找到dp[i][j]的最大元素和它对应的i和j就可以得到结果“s中最长回文子串”。
另外还有一个要注意的点：因为需要访问dp[i+1][j-1]，因此i是从大到小的，j是从小到大的。j从0到size-1，i从j-1到0。
char * longestPalindrome(char * s){
int len = strlen(s);
if(len <= 1) return s;
int dp[len][len];
for(int i = 0; i < len; i++){
for(int j = 0; j < len; j++){
dp[i][j] = i == j;
}
}
int start = 0;
int max = 1;
for(int j = 1; j < len; j++){
for(int i = j - 1; i >= 0; i--){
if(s[i] == s[j]){
if(j - i == 1)
dp[i][j] = 2;
else{
if(dp[i + 1][j - 1] > 0)
dp[i][j] = dp[i + 1][j - 1] + 2;
else
dp[i][j] = 0;
}
}
else
dp[i][j] = 0;
if(dp[i][j] >= max) {
max = dp[i][j];
start = i;
}
}
}
char *result = (char *)malloc((max + 1) * sizeof(char));
for(int i = 0;i < max; i++){
result[i] = s[start + i];
}
result[max] = '\0';
return result;
}
3、中心扩散法
思路：遍历输入的字符串s，以每个字符mid为中心，分别计算mid为中心的奇数位（例如"cabac"中以"b"为中心的回文字符串）和偶数位（例如"cabbac"以"bb"为中心的回文字符串）的最长回文字符串，记录最长回文字符串出现的起始下标及长度max。
char * longestPalindrome(char * s){
int len = strlen(s);
int start = 0;
int mid = 0;
int max = 0;
int extend = 0;
while(mid < len){
//计算形如 "cabbac"以"bb"为中心的回文字符串
extend = 0;
while(mid - extend >= 0 && mid + extend + 1 < len && s[mid - extend] == s[mid + extend + 1]){
extend++;
}
if(2 * extend >= max){
max = 2 * extend;
start = mid - extend + 1;
}
//计算形如 "cabac"中以"b"为中心的回文字符串
extend = 0;
while(mid - extend - 1 >= 0 && mid + extend + 1 < len && s[mid - extend - 1] == s[mid + extend + 1]){
extend++;
}
if(2 * extend + 1 >= max){
max = 2 * extend + 1;
start = mid - extend;
}
mid++;
}
char *result = (char *)malloc((max + 1) * sizeof(char));
for(int i = 0;i < max; i++){
result[i] = s[start + i];
}
result[max] = '\0';
return result;
}
4、中心扩散的改进算法
思路：中心扩散思路中，需要计算mid为中心的奇数位（例如"cabac"中以"b"为中心的回文字符串）和偶数位（例如"cabbac"以"bb"为中心的回文字符串）的最长回文字符串，现将输入的字符串左右填充特殊字符，即将输入字符"babacd"每两个字符之间分别填充字符""，变为"babbad"，可将所有字符均变为奇数个长度，从而避免了奇数位和偶数位分别判断，但该方法需要额外申请内存存储填充字符串，时间上并没有快，但可为后续时间复杂度为O(n)的方法提供思路。
char * longestPalindrome(char * s){
int len = strlen(s);
int new_len = 2 * len + 1;
char *new_s = (char *)malloc((new_len + 1) * sizeof(char));
int j = 0;
for(int i = 0; i < len; i++){
new_s[j++] = '*';
new_s[j++] = s[i];
}
new_s[j] = '*';
new_s[new_len] = '\0';
int start = 0;
int mid = 1;
int max = 0;
int extend = 0;
while(mid < new_len){
extend = 0;
while(mid - extend - 1 >= 0 && mid + extend + 1 < new_len && new_s[mid - extend - 1] == new_s[mid + extend + 1]){
extend++;
}
if(2 * extend + 1 >= max){
max = 2 * extend + 1;
start = mid - extend;
}
mid += 1;
}
char *result = (char *)malloc((max / 2 + 1) * sizeof(char));
for(int i = 0; i < max / 2; i++){
result[i] = new_s[start + 1 + 2 * i ];
}
result[max / 2] = '\0';
return result;
}
本系列文章，旨在打造LeetCode题目解题方法，帮助和引导同学们开阔学习算法思路，由于个人能力和精力的局限性，也会参考其他网站的代码和思路，如有侵权，请联系本人删除。
网友评论