题记： 尼玛没想到一个简单的回文字符串这么多的解法。 跪了。 不同的perspective， 看到的问题的不同的结构， 进而会完全影响你解决问题的思路。
注意， substring和subsequence 是有区别的。substring属于subsequence， 但是subsequence 不一定是substring。
给定一个string T = str[0…n-1]， 该字符串的一个子串substring就是截取连续的（包括全部）的一部分subT = [i, …j]， 其中， 0<= iand j <= n-1。 但是subsequence则是选择相关的字符， 保持其在原字符串中的相对顺序， 然后组成的新的string就是subsequence, 别混淆了。
最长回文子串（LPS）就是从给定的字符串中找出最长的一个子字符串， 这个子字符串从左往右读和从右往左读， 读出的结果是一样的。
例如：aba, a, abba均是回文子串。 在例如， S = "abcbcbb"的LPS 是“bcbcb”。
（方法一） bruteforce的办法： 最简单的办法就是价差字符串的每一个子字符串是否为palindrome or not。 我们可以运行三个loops, 外层两个loops 一个个的选择字符串所有可能的子字符串， 内层循环检查选的该子字符串是否是palindorme的。
#include <string>#include <iostream>using namespace std;/*判断str[i..j]是否为回文串*/bool isPalindrome(string str, int Start, int End) {while(str[Start++] == str[End–] && Start <= End) { }if(str[–Start] != str[++End]) {return false;} else {return true;}}/*返回最长回文子串长度*/string longestPald(string str) {int len = str.length();int longest = 1;if(len == 1) {return str.substr(0, 1);}int longestStart = 0;for(int i = 0; i<len; i++) {for(int j = i + 1; j < len; j++) {if(isPalindrome(str, i, j)) {if(longest < j – i + 1) {longestStart = i;longest = j – i + 1;}//longest = (longest < j-i+1 ? j-i+1: longest);}}}cout << longest << endl;return str.substr(longestStart, longest);}int main() {string s = "forgeeksskeegfor";cout << longestPald(s) << endl;return 0;}运行结果如下：
分析： 时间复杂度： O（n^3）
辅助空间复杂度： O（1）
(方法二) 动态规划的办法： 我们maintain一个boolean的table[n][n]， 然后自底向上的方式填充这个table。 如果子字符串str[i, j]是palindrome的 我们就把table[i][j]记为true， 否则就记为false。 为了计算table[i][j], 我们需要首先检查table[i+1][j-1]， 如果table[i+1][j-1]是true的， 并且str[i]与str[j]是相同的字符， 我们就记录table[i][j]为true。否则table[i][j]就为false。 更详细的分析见下面：
如果substring(i， j)是palindromic的, 那么substring(i+1, j-1)也是palindromic的。
table[i][j]是palindromic的， 那么几位true。 otherwise, 记为0。
当j – i 比较小的时候， 即为0或者为1， 那么我们很容易知道：
table[i][i] = true, table[i][i+1] = （S[i] == S[j]）, 这是base case。
另外， 还有table[i][j] = table[i + 1] [j – 1] && S[i]==S[j]。
table[i][i]如下：
table[i][i+1]如下：
table[i][i+2], table[i][i+3]等等如下：
程序如下：
#include <string>#include <cstring>#include <iostream>using namespace std;string longestPalindromeDP(string s) { int n = s.length(); int longestBegin = 0; int maxLen = 1; bool table[1000][1000]; memset(table, 0, sizeof(table[0][0]) * 1000 * 1000); // for substring of length 1 are palindrome for (int i = 0; i < n; i++) { table[i][i] = true; } //check for substring of length 2 for (int i = 0; i < n-1; i++) { if (s[i] == s[i+1]) { table[i][i+1] = true; longestBegin = i; maxLen = 2; } } // check for lengths greater than 2 // len is the length of substring for (int len = 3; len <= n; len++) { // fix the starting index for (int i = 0; i < n-len+1; i++) { int j = i+len-1; // checking for sub-string from ith index to // jth index iff str[i+1] to str[j-1] is a // palindrome if (s[i] == s[j] && table[i+1][j-1]) { table[i][j] = true; /*if(len > maxlen) { // 总是成立，， 所以可以去掉这个条件 longestBegin = i; maxLen = len; } */ longestBegin = i; maxLen = len; } } } return s.substr(longestBegin, maxLen);}int main() { string s = "forgeeksskeegfor"; cout << longestPalindromeDP(s) << endl; return 0;}运行结果如下：在你成功地把自己推销给别人之前，你必须百
