一个字符串的子串是字符串中连续的一个序列，而一个字符串的子序列是字符串中保持相对位置的字符序列，譬如，"adi"可以使字符串"abcdefghi"的子序列但不是子串。这也就决定了在解这两种"LCS"问题上的一些区别。
Longest-Common-Substring和Longest-Common-Subsequence是不一样的。
这个题的要求是求一个字符串里面的最长回文字符串，可以是不连续的。
笔试感受
之前写过一个求最长对称字符串的(http://www.jianshu.com/p/d23c6b0e02e2)，不过那个题求的是连续的。
我感觉腾讯这个题挺复杂的，是不是要DP什么的？
我当时想的是，头尾指针向中间移动，相等就++，不想等的话，跳一个；
可是问题来了，跳哪个呢？每一步都有两种情况啊。。
当时我也想不出别的思路了。
新的思考：
看LCS的解题过程的时候我想，借用一下的话，既然两个指针只能动一个，那我们分别递归，然后求最大值好了，这就是DP吧
*beg==*end;beg++;end++-
*beg!=*end:
return max(solution(beg++,end),solution(beg,end++))
如果我们只要求求出长度的话，还是比较简单的（但是我始终不得递归之法，写了半天写了个错的。。真是伤心，其实就差一点点了）
递归解法：
函数如下：
int solution_im(char* s, int beg, int end)
{
if (!s || beg > end)
return 0;
if (beg == end)
return 1;
if (s[beg] == s[end])
return solution_im(s, ++beg, --end) + 2;
else
{
int left = solution_im(s, ++beg, end);
int right = solution_im(s, beg, --end);
if (left > right)
return left;
else return right;
}
}
动态规划解法：
其实我前面在分析的时候已经把动态规划的方程写出来了：
*beg==*end;beg++;end++-
*beg!=*end:
return max(solution(beg++,end),solution(beg,end++))
但是动态规划解题的时候，会保存之前计算的结果，而不是简单的递归调用，这样效率可能高一点，但是会使用数组来保存数据。
这个题和lcs蛮相似的。
首先，如果我们不考虑输出字符串而只是输出回文子序列的长度的话，会简单一些。
转换一下思路，我们之前是求两个游标beg和end直接的长度，是从大往小求的。
我们现在从小往大求（最优子结构），我们依次求出长度为1，长度为2，3....一直求到n-1，这样每次计算都可以用之前的值了。
所以我们需要的矩阵的作用也是这样，保存从beg到end的值,记为a[beg][end].
具体实现如下：
int solution_dp(char*s)
{
if (!s)
{
return 0;
std::cout << "z";
}
int len = strlen(s);
int i = 0, j = 0;
int tmp;
int a[50][50] = { 0 };//a[i][j] means the length between i , j ;
for (i = 0; i < len; i++)
a[i][i] = 1;
for (i=1; i < len; i++)//i means the length of subsequence
{
tmp = 0;
for (j=0; j+i < len; j++)//length between j,j+i
{
if (s[j] == s[j + i])
tmp=a[j+1][j + i-1] + 2;
else
{
if (a[j + 1][j + i]>a[j][j + i - 1])
tmp = a[j + 1][j + i];
else
tmp = a[j][j + i - 1];
}
a[j][j + i] = tmp;
}
}
return a[0][len - 1];
}
如果要输出这个字符串呢？
其实加一个容器进去就好了，我直接使用了c++里面的vector:
int solution_dp(char*s)
{
if (!s)
{
return 0;
std::cout << "z";
}
std::vector<char> svec;
int len = strlen(s);
int i = 0, j = 0;
int tmp;
int a[50][50] = { 0 };//a[i][j] means the length between i , j ;
for (i = 0; i < len; i++)
a[i][i] = 1;
for (i=1; i < len; i++)//i means the length of subsequence
{
tmp = 0;
for (j=0; j+i < len; j++)//length between j,j+i
{
if (s[j] == s[j + i])
{
tmp = a[j + 1][j + i - 1] + 2;
svec.push_back(s[j]);
}
else
{
if (a[j + 1][j + i]>a[j][j + i - 1])
tmp = a[j + 1][j + i];
else
tmp = a[j][j + i - 1];
}
a[j][j + i] = tmp;
}
}
auto beg = svec.begin();
while (beg != svec.end())
std::cout << *beg++;
return a[0][len - 1];
}
只会输出一半的回文字符哦，要改也很简单。
思路3:
使用上次的LCS函数，另一个字符串是现有字符串的逆序，求两个字符串的common subsequence
暂时先不写了。
