LeetCode第五题：最长回文子串（C语言）

深碍√TFBOYSˉ_ 2022-04-22 08:50 151阅读 0赞

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

示例 1：

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

输入: “cbbd”  
输出: “bb”

--------------------

#### 解法一：暴力求解法 ####

思想：  
**反转 S，使之变成 S’。找到 S 和 S’之间最长的公共子串，这也必然是最长的回文子串。**  
理由：如果找两个字符串的公共子串，i指向第一个字符串，j指向第二个字符串，用暴力求解法肯定就是i每走一步，j就不断的从头遍历第二个字符串，然后判断是否相等。  
j从前往后走，就相当于原字符串从后向前走。  
S=“abacdfgdcaba” , S ′ =“abacdgfdcaba”：S 以及 S’ 之间的最长公共子串为 “abacd”，显然，这不是回文。所以我们要加一个判断条件就可以了。  
**暴力算法的时间复杂度为O(n^3)，在LeetCode中跑步过去，仅供参考**

//判断一个字符串是不是回文
    	int IfPlalindrome(char *s) { 
    		int count = strlen(s);
    		int left = 0;
    		int right = count - 1;
    		while (left < right)
    		{ 
    			if (s[left] != s[right])
    			{ 
    				return 0; //不是回文返回0，是回文返回1
    			}
    			left++;
    			right--;
    		}
    		return 1;
    	}
    	//反转字符串
    	char *reverse(char *s, int count)
    	{ 
    		char *p = (char *)malloc(sizeof(char) * (count + 1));
    		int i = 0;
    		for (; i < count; i++)
    		{ 
    			p[i] = s[count - i - 1];
    		}
    		p[i] = '\0';
    		return p;
    	}
    	
    	char* longestPalindrome(char* s) { 
    		int count = strlen(s);
    		//arr中存放的是最长的回文子串
    		char *arr = (char *)malloc(sizeof(char) * 1001);
    		char *p = reverse(s, count);
    		unsigned int max = 0;
    		//arr1中存放每一次循环遇见的回文子串
    		char arr1[2000];
    		for (int i = 0; i < count; i++) { 
    			for (int j = 0; j < count; j++) { 
    				int m = i;
    				int n = j;
    				int k = 0;
    				while (s[m] == p[n])
    				{ 
    					arr1[k] = s[m];
    					k++;
    					m++;
    					n++;
    				}
    				arr1[k] = '\0';
    				//判断是不是回文子串
    				if (IfPlalindrome(arr1))
    				{ 
    					//和arr中的回文子串长度作对比，大的话，就更新
    					if (strlen(arr1) > max)
    					{ 
    						max = strlen(arr1);
    						strcpy(arr, arr1);
    					}
    				}
    			}
    		}
    		return arr;
    	}

#### 解法二：动态规划 ####

在暴力求解法中，判断子串用了很多重复的操作，动态规划就是要尽量避免重复的操作。  
s的长度为N，生成一个N\*N的二维数组dp\[1001\]\[1001\]

*  dp\[i\]\[j\] 表示从s\[i\]到s\[j\]是否是回文
 *  dp\[i\]\[i\] = true 因为dp\[i\]\[i\]一定是回文
 *  在动态规划中只需要记录回文开始的位置和长度即可  
    **时间复杂度：O(n^2)**  
    **空间复杂度：O(N^2)**

char* longestPalindrome(char* s)
       { 
       	int len = strlen(s);
       	if (len <= 1) {  return s; }
       	//定义bool类型的dp，只能为true或false
       	bool dp[1001][1001];
       	memset(dp, 0, sizeof(dp));
       	dp[0][0] = 1;
       	for (int i = 1; i < len; i++)
       	{ 
       		dp[i][i] = true;
       		//一定不要忽略，在下面k=2会用到
       		dp[i][i - 1] = true;
       	}
       	int left = 0;
       	int right = 0;
       	int max = 0;
       	//k表示回文子串的长度
       	for (int k = 2; k <= len; k++)
       	{ 
       		//i表示回文子串的起始位置
       		for (int i = 0; i < len - k + 1; i++)
       		{ 
       			if (s[i] == s[k - 1 + i] && dp[i + 1][k + i - 2])
       			{ 
       				dp[i][k - 1 + i] = true;
       				if (max < k - 1)
       				{ 
       					max = k - 1;
       					left = i;
       					right = k - 1 + i;
       				}
       			}
       		}
       	}
       
       	char *arr = (char *)malloc(sizeof(int) * (max * 2));
       	int i = 0;
       	for (; i <= max; i++)
       	{ 
       		arr[i] = s[left++];
       	}
       	arr[i] = '\0';
       	return arr;
       }

#### 解法三：中心扩展法 ####

以某个元素为中心，分别计算偶数长度的回文最大长度和奇数长度的回文最大长度。  
**时间复杂度O(N^2)**

char* longestPalindrome(char* s)
    	{ 
    		int len = strlen(s);
    		if (len <= 1) {  return s; }
    		int start = 0;
    		int maxlen = 0;
    		//i表示中间元素下标
    		for (int i = 1; i < len; i++)
    		{ 
    			//偶数长度
    			int low = i - 1;
    			int high = i;
    			while (low >= 0 && high < len && s[low] == s[high])
    			{ 
    				low--;
    				high++;
    			}
    			if (high - low - 1 > maxlen)
    			{ 
    				maxlen = high - low - 1;
    				start = low + 1;
    			}
    			//奇数长度
    			low = i - 1; high = i + 1;
    			while (low >= 0 && high < len && s[low] == s[high])
    			{ 
    				low--;
    				high++;
    			}
    			if (high - low - 1 > maxlen)
    			{ 
    				maxlen = high - low - 1;
    				start = low + 1;
    			}
    		}
    		char *arr = (char *)malloc(sizeof(int) * (maxlen * 2));
    		int i = 0;
    		for (; i < maxlen; i++)
    		{ 
    			arr[i] = s[start++];
    		}
    		arr[i] = '\0';
    		return arr;
    	}