首页 > 代码库 > [LeetCode]Longest Palindromic Substring

[LeetCode]Longest Palindromic Substring

2024-09-12 13:53:01   213人阅读

查找最长回文子串

思路：

一个指针从头部，一个指针从尾部，对比每一个字母，若相等则可能是回文子串，则，检测子串是否回文，是则比较和已知的子串长度，更长就记录其起始和终止坐标，否则就放弃。

 1 /**********************************************************************
 2 Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
 3 Example:
 4 Input: "babad"
 5 Output: "bab"
 6 Note: "aba" is also a valid answer.
 7 Example:
 8 Input: "cbbd"
 9 Output: "bb"
10 **********************************************************************/
11 #include <stdio.h>
12 #include <ctype.h>
13 
14 char* longestPalindrome(char* s) {
15     int length = strlen(s);
16     int i,j,max = 1,maxi = 0,maxj = 0,flag = 1;//flag标志是否是回文子串
17     for(i = 0;i < length && i + max < length;i++){//从头开始检测，最后剩余未检测长度少于一直最长解则放弃
18         for(j = length - 1;j > i;j--){//从尾部开始检测
19             flag = 1;
20             if(s[i] == s[j]){//可能回文
21                 int head = i + 1,tail = j - 1;
22                 while(head < tail){//检测是否是回文子串
23                     if(s[head] != s[tail]){
24                         flag = 0;
25                         break;
26                     }
27                     head++;
28                     tail--;
29                 }
30                 if(flag == 1){//如果是回文子串
31                     if(max < j - i + 1){//长度是否比已知最优解长
32                         max = j - i + 1;
33                         maxi = i;
34                         maxj = j;
35                     }
36                     break;//继续收缩尾部指针，也得不到更优的解，所以放弃
37                 }
38             }
39         }
40     }
41 
42     char *substr = (char *)malloc((max + 1)*sizeof(char));
43     memset(substr,0,(max + 1)*sizeof(char));
44     strncpy(substr,s + maxi,max);
45     return substr;
46 }
47 
48 void main(){
49     char s[] = "babadada";
50     char *sp = longestPalindrome(s);
51     printf("%s\n",sp);
52     free(sp);
53 }

上面的思路是从两边向中间收束，另一个思路是从中间向两边发散。

具体如下：

先找当前下标为中心的回文子串，比较它和最优解，更优则更新最优解，

递归查找中心点向左和向右偏移后的回文子串。

 1 /**********************************************************************
 2 Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
 3 Example:
 4 Input: "babad"
 5 Output: "bab"
 6 Note: "aba" is also a valid answer.
 7 Example:
 8 Input: "cbbd"
 9 Output: "bb"
10 **********************************************************************/
11 #include <stdio.h>
12 #include <ctype.h>
13 
14 int max = 1;//记录已知最长的回文子串的长度
15 int maxi = 0;//记录已知最长的回文子串的头部坐标
16 int maxj = 0;//记录已知最长的回文子串的尾部坐标
17 
18 void longestPSubstring(char *s,int i){//记录当前搜索的位置
19     int head = i - 1;
20     int tail = i + 1;
21     int length = strlen(s);
22     while((head >= 0 || tail < length) && s[head] == s[tail]){//检测以i为中心的回文子串
23         head--;
24         tail++;
25     }
26     if(tail - head - 1 > max){//比较以i为中心的回文子串是否更长
27         maxi = head + 1;
28         maxj = tail - 1;
29         max = tail - head - 1;
30     }
31     
32     if(i - 1 > 0){
33         longestPSubstring(s,i - 1);//向左偏移
34     }
35     if(i + 1 < length - 1){
36         longestPSubstring(s,i + 1);//向右偏移
37     }
38 }
39 
40 char* longestPalindrome(char* s) {
41         int length = strlen(s);
42     longestPSubstring(s,length/2);
43 
44     char *substr = (char *)malloc((max + 1)*sizeof(char));
45     memset(substr,0,(max + 1)*sizeof(char));
46     strncpy(substr,s + maxi,max);
47     return substr;
48 }
49 
50 void main(){
51     char s[] = "babadada";
52     char *sp = longestPalindrome(s);
53     printf("%s\n",sp);
54     free(sp);
55 }

 

[LeetCode]Longest Palindromic Substring


联系
我们