Longest Palindromic Substring：最长回文子串

Longest Palindromic Substring：最长回文子串2015-02-11题目链接

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

求字符串的最长回文子串

算法1：暴力解法，枚举所有子串，对每个子串判断是否为回文，复杂度为O（n^3）

算法2：删除暴力解法中有很多重复的判断。很容易想到动态规划，时间复杂度O（n^2）,空间O（n^2）,动态规划方程如下：

dp[i][j] 表示子串s[i…j]是否是回文

初始化：dp[i][i] = true （0 <= i <= n-1）; dp[i][i-1] = true （1 <= i <= n-1）; 其余的初始化为false

dp[i][j] = （s[i] == s[j] && dp[i+1][j-1] == true）

在动态规划中保存最长回文的长度及起点即可

class Solution {public:string longestPalindrome（string s） {const int len = s.size（）;if（len <= 1）return s;bool dp[len][len];//dp[i][j]表示s[i..j]是否是回文memset（dp, 0, sizeof（dp））;int resLeft = 0, resRight = 0;dp[0][0] = true;for（int i = 1; i < len; i++）{dp[i][i] = true;dp[i][i-1] = true;//这个初始化容易忽略，当k=2时要用到}for（int k = 2; k <= len; k++）//枚举子串长度for（int i = 0; i <= len-k; i++）//枚举子串起始位置{if（s[i] == s[i+k-1] && dp[i+1][i+k-2]）{dp[i][i+k-1] = true;if（resRight-resLeft+1 < k）{resLeft = i;resRight = i+k-1;}}}return s.substr（resLeft, resRight-resLeft+1）;}};

算法3：以某个元素为中心，分别计算偶数长度的回文最大长度和奇数长度的回文最大长度。时间复杂度O（n^2），空间O（1）

class Solution {public:string longestPalindrome（string s） {const int len = s.size（）;if（len <= 1）return s;int start, maxLen = 0;for（int i = 1; i < len; i++）{//寻找以i-1,i为中点偶数长度的回文int low = i-1, 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;} //寻找以i为中心的奇数长度的回文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;}}return s.substr（start, maxLen）;}};