Longest Palindromic Substring
Given a stringS, find the longest palindromic substring inS. You may assume that the maximum length ofSis 1000, and there exists one unique longest palindromic substring.
对于这道题，要怎么设计这个table就是非常难想到的事情。因为要利用一个二维数组，把二维数组的两个下标作为标示主串里面的两个字符位置，实在是够难想到的了。
什么时候使用动态规划法：
• Optimal substructure
• Overlapping subproblems
构建解的方法：
Characterize structure of optimal solution
Recursively define value of optimal solution
Compute in a bottom-up manner
如果是用暴力法的话，就需要O(n^3) 时间效率了，但是使用动态规划法，就只需要O(n^2)的时间复杂度了。
最难想的地方：P代表一个表，比较难想的就是P表的下标i和j代表原字符串中的两个前后下标s[i]和s[j]的位置。
如果P[i,j]为真，当且仅当si-1,si-2...sj-1,sj这一个子串都为palindrome。例如：s[] = skrdjdre那么P[2][6] = true，因为s[2]=r=s[6],且djd为回文。
不明白，可以看下表，动手填一填，未填出的都初始化为false,其中t代表填写true：
2014-1-24 Update
Leetcode有更新了，增加了两个大数据测试，一般使用vector容器的动态规划法超时了，而且也禁止了使用二维数组，会报错memory limit exceeded。
所以更新下动态规划法，使用3个一维数组，测试通过，不过时间大概为836ms，还是最下面的两边扩展计算的解法最优了。
class Solution {
public:
string longestPalindrome(string s)
{
int index = 0, len = 1;
int table[3][1000] = {1};
int last = -1; int cur = 1;
for (int i = 0; i < s.length(); i++)
{
table[0][i] = 1;
}
for (int i = 1; i < s.length(); i++)
{
if (s[i] == s[i-1])
{
table[cur][i] = 2;
index = i-1;
len = 2;
}
else table[cur][i] = 0;
}
for (int d = 2; d < s.length(); d++)
{
cur = (cur+1)%3; last = (last+1)%3;
for (int i = 0, j = d; j < s.length(); i++, j++)
{
if (s[i] == s[j] && table[last][j-1] != 0)
{
table[cur][j] = table[last][j-1]+2;
if (table[cur][j] > len)
{
len = table[cur][j];
index = i;
}
}
else table[cur][j] = 0;
}
}
return s.substr(index, len);
}
};下面就是实现上述思想的程序，时间复杂度O(n*n),空间复杂度O(n*n)
string longestPalindrome(string s)
{
int n = s.length();
vector<vector<bool> > table;
vector<bool> temp(n, false);
for (int i = 0; i < n; i++)
{
table.push_back(temp);
table[i][i] = true;
}
//Attention: Don't forget we need two centor for palindrome
int subStartPoint = 0;
int maxLength = 1;
for (int i = 1; i < n; i++)
{
if (s[i-1] == s[i])
{
table[i-1][i] = true;
subStartPoint = i-1;
maxLength = 2;
}
}//for
for (int k = 3; k <= n; k++)
{
for (int i = 0; i <= n-k; i++)
{
int j=k+i-1;
if (s[i] == s[j] && table[i+1][j-1] == true)
{
table[i][j] = true;
if(maxLength < k)
{
subStartPoint = i;
maxLength = k;
}
}
}//for(int i = 0...
}//for(k=3...
return s.substr(subStartPoint, maxLength);
}实际leetcode运行速度：
但是其实有更加简单的方法，实际运行速度更加快。
思想：
1. 以每个s[i]字符为中心，两边测试看以这个字符为中心的回文长度是多少
2. 以每两个字符s[i-1]s[i]为中心，测试这两个字符是否相等，和以这两个字符为中心的回文有多长
最后记录最大长度和最大长度子串起点
其实我觉得这个算法比前面的算法还好理解：
int testTwoSides(string &s, int low, int up)
{
int n = s.length();
int max = 0;
if (low == up)
{
low--;
up++;
max = 1;
}
while (low>=0 && up<n && s[low] == s[up])
{
max+=2;
low--;
up++;
}
return max;
}
string longestPalindrome(string s)
{
int n = s.length();
int subStartPoint = 0;
int maxLength = 1;
int temp = 0;
for (int i = 0; i < n; i++)
{
temp = testTwoSides(s, i, i);
if (temp > maxLength)
{
subStartPoint = i - temp/2;
maxLength = temp;
}
}
for (int i = 1; i < n; i++)
{
temp = testTwoSides(s, i-1, i);
if (temp > maxLength)
{
subStartPoint = i - temp/2;
maxLength = temp;
}
}
return s.substr(subStartPoint, maxLength);
}
理论上这个算法的时间复杂度是O(n*n)，空间复杂度O(1);
记得前段时间看到某博主对于类似的这样的算法说成时间复杂度是O(n)，所以明确说明这个时间复杂度是：O(n*n)
计算起来有点麻烦，至于是如何计算的，因为牵涉单概率论的知识和算法时间复杂度计算基础知识，虽然不算很难的概率论知识，但是不是那么容易讲明白的。怕讲不好，而且也不用那么麻烦每个算法都那么正规的分析，不然就累死人额。
所以可以对于这个算法可以给出特定例子走一走，比如对于串aaaaaaaaaaa，那么它就是最坏情况的时间复杂了。
实际运行效果却是出奇的好：
2013/12/7 update:
上面的算法其实可以利用一个循环就可以了，不需要多一个循环，不过时间效率一样。应该可以稍微优化一点吧。
class Solution {
public:
string longestPalindrome(string &s)
{
int startPoint = 0;
int maxLen = 1;
for (int j = 1; j < s.length(); j++)
{
int t = testTwoSides(s, j, j);
if (t > maxLen)
{
startPoint = j - t/2;
maxLen = t;
}
t = testTwoSides(s, j-1, j);
if (t > maxLen)
{
startPoint = j - t/2;
maxLen = t;
}
}
return s.substr(startPoint, maxLen);
}
int testTwoSides(string &s, int low, int up)
{
int n = s.length();
int max = 0;
if (low == up)
{
low--;
up++;
max = 1;
}
while (low>=0 && up<n && s[low] == s[up])
{
max+=2;
low--;
up++;
}
return max;
}
};leetCode网站上的分析的不错了：
http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html