题目：
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、动态规划法：（一般含“最XX”等优化词义的题意味着都可以动态规划求解），时间复杂度O(n^2)，空间复杂度O(n^2)。
形如"abba", "abbba"这样的字符串，如果用dp[i][j]表示从下标i到j之间的子字符串所构成的回文子串的长度，则有：
dp[i][j] = dp[i+1][j-1] && s[i] == s[j]
初始化：
奇数个字符：dp[i][i] = 1; 偶数个字符：dp[i][i+1] = 1
1 //动态规划法 2 string LongestPalindromicStringDP(string str) 3 { 4 size_t n = str.size(); 5 if (n == 0 || n == 1) 6 return str; 7 //创建dp二维数组 8 //d[i][j] = dp[i+1][j-1] && s[i] == s[j] 9 bool **dp = new bool *[n]; 10 for (size_t i = 0; i < n; ++ i) 11 dp[i] = new bool[n]; 12 13 int nLongestIndex = 0; //最长回文子串的开始下标 14 int nMaxLen = 0; //长度 15 16 for (size_t i = 0; i < n; i ++) 17 for (size_t j = 0; j < n; j ++) 18 dp[i][j] = false; 19 for (size_t i = 0; i < n; ++ i) 20 dp[i][i] = true; //初始化一个字母 21 22 for (size_t i = 0; i < n - 1; ++ i) { 23 if (str[i] == str[i+1]) { 24 dp[i][i+1] = true; //初始化两个相同的字母"aa" 25 nLongestIndex = i; 26 nMaxLen = 2; 27 } 28 } 29 //从长度3开始操作, (aba)ba, a(bab)a, ab(aba) 30 for (size_t len = 3; len <= n; ++ len) { 31 for (size_t i = 0; i < n-len+1; ++ i) { 32 size_t j = i + len - 1; 33 if (str[i] == str[j] && dp[i+1][j-1]){ 34 dp[i][j] = true; 35 nLongestIndex = i; 36 nMaxLen = len; 37 } 38 } 39 } 40 41 //释放dp 42 for (size_t i = 0; i < n; ++ i) 43 delete []dp[i]; 44 delete []dp; 45 46 return str.substr(nLongestIndex, nMaxLen); 47 }
3、中心扩散法：时间复杂度O(n^2)，空间复杂度O(1)
顾名思义，从一个节点，分别向两边扩散，用两个指针分别向前向后遍历。
1 //中心扩散法 2 string LongestPalindromicString(string str) 3 { 4 size_t n = str.size(); 5 if (n == 0 || n == 1) 6 return str; 7 8 size_t start = 0; 9 size_t nMaxLen = 0; 10 11 for (size_t i = 0; i < n; ++ i) { 12 size_t j = i, k = i; //分别从中心向两边扩散 13 while(k < n-1 && str[k] == str[k+1]) 14 k++; //有相同字母的情况："aaa" 15 while(j > 0 && k < n-1 && str[j-1] == str[k+1]){ 16 k++; //不同字母情况: "aba" 17 j--; 18 } 19 if(k-j+1 > nMaxLen){ 20 nMaxLen = k-j+1; 21 start = j; 22 } 23 } 24 return str.substr(start, nMaxLen); 25 }
4、很明显，这两种方法时间复杂度还是太高了，还有一种算法叫Manacher，时间复杂度能够降为O(n)，空间复杂度也为O(n)，先记下，以后再做研究吧。
