LeetCode最长回文子串——C

灰太狼 2022-01-07 23:09 231阅读 0赞

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/longest-palindromic-substring][https_leetcode-cn.com_problems_longest-palindromic-substring]

## 题目 ##

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：  
输入: “babad”  
输出: “bab”  
注意: “aba” 也是一个有效答案。

示例 2：  
输入: “cbbd”  
输出: “bb”

## 题解 ##

要想求最长回文子串，就要理解什么是回文，简单来说就是正读（写）和反读（写）是一样的，而不是简单的成镜像。

**范例：上海自来水来自海上**  
**反例：abcda（其中 b 和 d 是不一样的，不是回文）**

我想的最容易理解的应该是中心扩展法，回文中心的两侧互为镜像，且字符一样。  
这样我们要考虑的就是这个中心，是一个还是两个一样的，毕竟都可以组成回文  
**1、第一种方法就是先判断这个和下一个是否一样，再判断是以该字符为中心左右扩展，还是以这两个字符为中心左右扩展。（但是要是三个一样就会出问题，所以不采用第一种）**

**2、第二种方法就是把该字符，该字符及下一个字符都同时中心扩展，判断哪个中心扩展值大，就选哪个。**

## 代码 ##

**记得提交的时候把汉字注释去掉，不然会报内部出错**

int max(int x,int y){
    	return x>y?x:y;
    }
    
    int centerExpand(char* s,int left,int right,int len){
    	while(left>=0 && right<len && s[left]==s[right]){
            left--;									//判断是否相等，相等就向两边继续扩展 
            right++;
        }
        return right-left-1;
    }
     
    char* longestPalindrome(char* s){
    	int L=0;									//记录回文子串最大长度 
    	int start=0;								//记录回文子串开始位置 
    	int end=0;									//记录回文子串截至位置 
    	int len=strlen(s);
    	if(len==0||len==1)							//一个一下直接返回 
            return s;
    	for(int i=0;i<len;i++){
    		int l1=centerExpand(s,i,i,len);			//以 i 为中心的扩展 
    		int l2=centerExpand(s,i,i+1,len);		//以 i 和 i+1 为中心的扩展 
    		L=max(max(l1,l2),L);					//取最大长度为最大回文子串 
    		
    		if(L>end-start+1){
    			start=i-(L-1)/2;					//修改开始位置 
    			end=i+L/2;							//修改截至位置 
    		}
    	}
    	
    	char* p=(char*)malloc(sizeof(char)*(L+1));	//分配空间（长度加一个截至符） 
    	strncpy(p,s+start,L);						//复制（从 s+start 到后面的 L 长度的字符） 
    	p[L] = '\0';								//截至符 
    	return p;
    }

## 调试结果 ##

#include<stdio.h>
    #include<string.h>
    #include<malloc.h>
    
    int main(){
    	char* s=(char*)"cbbd";
    	char* p=longestPalindrome(s);
    	
    	while(*p!='\0'){
    		printf("%c",*p);
    		p++;
    	}
    	
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]

[https_leetcode-cn.com_problems_longest-palindromic-substring]: https://leetcode-cn.com/problems/longest-palindromic-substring
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190630123757290.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]: /images/20211220/a5f8aa893db34ea1a15eb3be10becb07.png