Description
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example
Input: “babad” Output: “bab” Note: “aba” is also a valid answer.
Input: “cbbd” Output: “bb”
Discussion
这道题可以采用动态规划的算法。我们维护一个二维数组dp。dp[i][j]表示从i到j是否是一个回文串。
递推式关系为：
如果dp[i+1][j-1] == 1 && s[i] == s[j]，则dp[i][j] = 1
算法的时间复杂度为O(n^2)。
C++ Code
class Solution {
public:
string longestPalindrome(string s) {
int ** dp;
dp = new int * [s.length()]; //保存子串i～j是否是回文串
for(int i = 0; i < s.length(); i++)
{
dp[i] = new int[s.length()];
}
for(int i = 0; i < s.length(); i++)
{
for(int j = 0; j < s.length(); j++)
{
//把只有一个字符的串初始化为1，其他为0
if(i < j)
{
dp[i][j] = 0;
}
else
{
dp[i][j] = 1;
}
}
}
int maxLen = 0;
int answer_startLoc = 0;
int answer_endLoc = 0;
for(int len = 1; len < s.length(); len++)
{
for(int startLoc = 0; startLoc < s.length() - len; startLoc++)
{
//如果原子串是一个回文串，则在该子串前后添加两个相同的字符得到的新串也是回文串
if(s[startLoc] == s[startLoc + len] && dp[startLoc + 1][startLoc + len - 1] == 1)
{
dp[startLoc][startLoc + len] = 1;
if(len > maxLen)
{
maxLen = len;
answer_startLoc = startLoc;
answer_endLoc = startLoc + len;
}
}
}
}
return s.substr(answer_startLoc, answer_endLoc - answer_startLoc + 1);
}
};