Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
78 lines (70 sloc) 2.26 KB
problem:
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.
solution:
思路一:O(n3)
暴力搜索法。枚举出所有的子串(O(n2)),并且依次检查子串是否是回文(O(n)),所以需要的总时间复杂度是O(n3)
思路二:Time:O(n2),Space:O(n2)
动态规划法。运用回文的性质:F(i,j) = F(i+1,j-1)if s[i] == s[j].其中F(i,j)被定义为子串s[i...j]是否是回文。所以枚举长度从1~N的子串(O(n2)),再判断是否为回文(O(1)).总体时间复杂度O(n2), 空间复杂度O(n2)。注意字符串为空和字符串长度为1时的特殊处理
//////////////////////
string longestPalindrome(string s)
{
if(s == "")
return "";
else if(s.length() == 1)
return s;
bool isPalindrome[1000][1000] = {false};
int longestBegin = 0;
int maxLen = 0;
for(int i = 0; i < s.length(); i++)
{
isPalindrome[i][i] = true;
if(i < s.length() - 1 && s[i] == s[i+1])
{
isPalindrome[i][i+1] = true;
longestBegin = i;
maxLen = 2;
}
}
for(int len = 3; len <= s.length(); len++)
for(int i = 0; i < s.length() - len + 1; i++)
{
int j = i + len - 1;
if(s[i] == s[j] && isPalindrome[i+1][j-1])
{
isPalindrome[i][j] = true;
longestBegin = i;
maxLen = len;
}
}
return s.substr(longestBegin, maxLen);
}
思路三:Time:O(n2),Space:O(1)
考虑到回文是关于其中心对称,所以一个回文可以从它的中心往两边扩散,并且回文串有2N-1个这样的中心(中心或者在任意一个字符或者在任意两个字符的之间)。从中心扩展回文需要时间O(n),所以总的时间复杂度O(n2).
///////////////////////////////////
string expandAroundCenter(string s, int l, int r)
{
int n = s.length();
while(l >= 0 && r <= n-1 && s[l] == s[r])
{
l--;
r++;
}
return s.substr(l + 1, r- l -1);
}
string longestPalindrome(string s)
{
int n = s.length();
if(n == 0)
return "";
string longest = s.substr(0,1);
for(int i = 0; i < n-1; ++i)
{
string p1 = expandAroundCenter(s, i, i);
if(p1.length() > longest.length())
longest = p1;
string p2 = expandAroundCenter(s, i, i+1);
if(p2.length() > longest.length())
longest = p2;
}
return longest;
}