Longest Palindromic Substring
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.
http://www.lintcode.com/en/problem/longest-palindromic-substring/
Discussion
这个题有很多种解法。暴力，动规。要熟悉。
Sulution 1
Brute force。判断每一个substring是否为palindrome，返回最长的那个。总共有C(N,2)个substring，判断回文复杂度为O(N)。所以是$$O(N^3)$$ 的runtime，O(1) space。
判断回文的方法见题目Valid Palindrome。
class Solution {
public:
/**
* @param s input string
* @return the longest palindromic substring
*/
string longestPalindrome(string& s) {
// Write your code here
int n = s.length();
int maxlen = 0;
string result;
for (int i=0; i<n; i++) {
for(int j=i; j<n; j++) {
//string tmp (s.begin()+i, s.begin()+j);//当i=j时，tmp是空的，所以不行，用substr函数。
string tmp = s.substr(i, j-i+1);
if(isPalindrome(tmp)) {
if(tmp.length() > maxlen) {
maxlen = tmp.length();
result = tmp;
}
}
}
}
return result;
}
private:
bool isPalindrome(string& s) {
// Write your code here
if (s.length()==0)
return true;
int begin = 0;
int end = s.length()-1;
while(begin< end) {
if(isalnum(s[begin]) == false)
begin++;
if(isalnum(s[end]) == false)
end--;
if(begin>=end)
break;
if(tolower(s[begin]) != tolower(s[end]) )
return false;
begin++;
end--;
}
return true;
}
};
Solution 2
DP.
- state: f[i][j]表示从i到j的substring是回文
- 状态转移：f[i][j] = f[i+1][j-1] && s[i]==s[j]. aba是回文是因为b是回文，两头两个a相同。
- initialize: f[i][i]=true, f[i][i+1]= (s[i]==s[i+1])
- answer: 记录最大长度和开始结束位置。
用一个string"ababa"画状态转移图，coding就不难了。
O(n^2) runtime, O(n^2) space.
class Solution {
public:
/**
* @param s input string
* @return the longest palindromic substring
*/
string longestPalindrome(string& s) {
string result;
if(s.length() ==0) return result;
int n = s.length();
int max_len = 1;
vector<vector<bool>> is_palindrome(n, vector<bool>(n, false));
int start_pos = 0;
for(int i=0; i<n-1; i++) {
is_palindrome[i][i] = true;
if(s[i]==s[i+1]) {
is_palindrome[i][i+1] = true;
max_len = 2;
start_pos = i;
}
}
is_palindrome[n-1][n-1] = true;
for(int i=n-1; i>=0; i--) {
for(int j=i+2; j<n; j++) {
if(s[i]==s[j] && is_palindrome[i+1][j-1]) {
is_palindrome[i][j] = true;
if(j-i+1 > max_len) {
max_len = j-i+1;
start_pos = i;
}
}
}
}
return s.substr(start_pos, max_len);
}
};
用滚动数组加自底向上的递归来改进为O(n) space。根据状态转移的实际例子是不难想出滚动数组的使用的。
class Solution {
public:
/**
* @param s input string
* @return the longest palindromic substring
*/
string longestPalindrome(string& s) {
// Write your code here
int n = s.length();
vector<bool> f(n, false);
int maxlen = 0;
int start = 0;
int end = 0;
// f[0] = true;
for(int j=0; j<n; j++) {
for (int i=0; i<=j; i++) {
if(i==j) {
f[i] = true;
} else if (j-i ==1) {
f[i] = (s[i] == s[i+1]);
} else {
f[i] = (s[i]==s[j] && f[i+1]);
}
if(f[i] && maxlen<j-i+1) {
maxlen = j-i+1;
start = i;
end = j;
}
}
}
return s.substr(start, end-start+1);
}
};
Solution 3
可以从一个给定位置，或者两个相邻的给定位置，往两侧扩展，得到新的substring回文。O(n^2) runtime, O(1) space.
class Solution {
public:
/**
* @param s input string
* @return the longest palindromic substring
*/
string longestPalindrome(string& s) {
// Write your code here
int n=s.length();
string result;
for(int i=0; i<n; i++) {
string odd, even;
odd = extendPalindrome(s, i, i);
if(i<n-1)
even = extendPalindrome(s, i, i+1);
if(odd.length() > result.length()) {
result = odd;
}
if(even.length() > result.length()) {
result = even;
}
}
return result;
}
private:
string extendPalindrome(string s, int start, int end) {
bool ind = false;
string result;
while (start <=end && start >=0 && end<s.length()) {
if(s[start] == s[end]) {
start--;
end++;
ind = true;
} else {
break;
}
}
if(ind) {
start++;//这里容易漏掉，防止出错的办法就是根据一个实例写code。
end--;
result = s.substr(start, end-start+1);;
}
return result;
}
};
这个思路更简洁的写法：
string expandAroundCenter(string s, int c1, int c2) {
int l = c1, r = c2;
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 longestPalindromeSimple(string s) {
int n = s.length();
if (n == 0) return "";
string longest = s.substr(0, 1); // a single char itself is a palindrome
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;
}
如果严格按照一个test case写code，会发现好多details，根据思想直接写是很难考虑到这些details的。养成test case的习惯。。。
竟然还有O(n)的算法，见reference 【2】。