leetcode--最长回文串（C语言）

题目：给定你一个字符串s，要求编写代码找出他最长的回文串。

解释：回文串就是从头到尾读和从尾到头读都是一样的。比如“aba”

栗子：

输入：s="abcabcb"

输出："abc"或者"bcb"

输入："abbc"

输出："bb"

提示：

1<=s.length<=1000;

其中字符串s只包含数字字符和字母字符

请完成下面函数：

其中s是输入的字符串

char * longestPalindrome(char * s){

}

我的思路一开始就是动态规划，因为动态规划是解决最值问题的算法。

那么就先来讲解一下动态规划算法怎么来解决这道题。

方法1：动态规划

首先我们需要做的就是找到他的状态方程，简单来说就是寻找它的规律方程。

这里以“ababc”为例。其中“aba”和“bab”都是回文串，如果在回文串“aba”去掉a变为“b”，显然还是回文串。再举个栗子进一步说明“abbabba”，显然最长的回文串就是“abbabba”，将回文串去掉左右两边的a变为“bbabb”，显然还是回文串，再去掉左右两边的b变为“bab”依然是回文串....

从上面的分析，聪明的同学一定找出了规律了。规律就是回文串里面依然是回文串。

这时得到的状态方程为： dp[i][j] = (s[i]==s[j] && dp[i+1][j-1]);

解释：dp[i][j]=true含义是从第i个字符到第j个字符之间的字符串是最长的回文串

接下来就是要确定边界条件了。

如果字符串长度为1的话显然是回文串，也就是单个字符是回文串

dp[i][j]=true,当i==j时成立。

 整体代码：

方法二：中心拓展法

对这个算法讲解一下。借助上面的DP算法，如果是回文串的话，那么它的内部依然也是回文串 。显然它是对称的，那么取它的中心，然后往两边扩展，如果遇到不是回文串的时候返回。具体举个栗子来说明：

假设输入s="abcbacd",当然输出的最长回文串就是"abcba"

从第一个位置开始出发，往两边扩散寻找它的最长回文串，一直到字符串最后一个字符为止。

假设此时需要寻找的是字符c最长的回文串，该怎么取寻找呢？

步骤：

首先先往左一个一个寻找，如果左边与其相同，继续往左寻找，直到遇到不相同为止。

然后往右边一个一个寻找，如果右边与其相同，继续往右寻找，直到遇到不相同为止。

最后往左右两边扩散寻找，直到不相同为止。

下面是leetcode上面一位解释的比较清楚的大佬解题过程。 

 

整体代码：