5. 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.
Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example:
Input: "cbbd"
Output: "bb"
Show Company Tags
Show Tags
Show Similar Problems
S1: naive enumeration
以每个字符为轴往左右查找palindromic substring
string longestPalindrome(string s) {
int size = s.size();
if(size < 1) return "";
string substring = s.substr(0,1);
for(int i = 1; i < size; ++i){
if(s[i] == s[i-1]){
int j = 1;
while(i+j < size && i-j > 0 && s[i+j] == s[i-j-1]) j++;
if(2*j > substring.size()) substring = s.substr(i-j, 2*j);
}
if(i - 2 >= 0 && s[i] == s[i-2]){
int j = 1;
while(i+j< size && i-2-j >= 0 && s[i+j] == s[i-2-j]) j++;
if(2*j+1 > substring.size()) substring = s.substr(i-j-1, 2*j+1);
}
}
return substring;
}
S2:enumeration with prunning
如果子串中有许多连续重复字母的话，可以进一步优化。最长回文子串的对称轴一定处在任意个连续的重复字母的中心。不然会导致回文子串短于这些连续字母。
这样可以每次扫描一段连续重复字母的左右位置，作为扩展的起始位置。
string longestPalindrome(string s) {
string result = "";
for (int left = 0, right = left; left < s.size(); left = right) {
right = left + 1;
//跳过重复字符
while (right < s.size() && s[right] == s[right-1]) {
right++;
}
//尝试向两边扩张
int curLeft = left - 1, curRight = right;
while (curLeft >= 0 && curRight < s.size() && s[curLeft] == s[curRight]) {
curLeft--;
curRight++;
}
int len = curRight - curLeft - 1;
if (len > result.size()) {
result = s.substr(curLeft + 1, len);
}
}
return result;
}
S3: DP
isPal[i][j]表示s[j]到s[i]是palindrome
//error注意：没有通过aabaaa的test case, output "maaa"没看出来为何
string longestPalindrome(string& s) {
string result = "";
int n = s.size();
if (n <= 1) {
return s;
}
vector<vector<bool>> isPal(n, vector<bool>(n, false));
isPal[0][0] = true;
for (int i = 1; i < n; ++i) {
isPal[i][i] = true;
isPal[i][i-1] = s[i] == s[i-1];
if (isPal[i][i-1] && result.size() < 2) {
result = s.substr(i-1, 2);
}
for (int j = i - 2; j >= 0; --j) {
isPal[i][j] = (isPal[i-1][j+1] && s[i] == s[j]);
if (isPal[i][j] && j - i + 1 > result.size()) {
result = s.substr(j, i - j + 1);
}
}
}
return result;
}
214. Shortest Palindrome
Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.
For example:
Given "aacecaaa", return "aaacecaaa".
Given "abcd", return "dcbabcd".
S1: naive enumeration
从数组的中间开始，穷举所有以s[i]为中心的palindrome，直到得到结果。注意s[i]取最优解的情况是以s[i+1]为轴而不是以s[i]和s[i+1]之间为轴。
string shortestPalindrome(string s) {
int size = s.size();
for(int mid = size/2-1; mid >= 0; --mid){
int j = 0;
while(mid-j >= 0 && mid+2+j < size && s[mid-j] == s[mid+2+j]) j++;
if(mid-j < 0){
string result = "";
for(int i = size-1; i >= 2*mid+3; --i)
result += s[i];
result += s;
return result;
}
else{
j = 0;
while( mid-j >= 0 && mid+1+j < size && s[mid-j] == s[mid+1+j]) j++;
if(mid-j < 0){
string result = "";
for(int i = size-1; i >= 2*(mid+1); --i)
result += s[i];
result += s;
return result;
}
}
}
string result = "";
for(int i = size-1; i > 0; --i) result += s[i];
result += s;
return result;
}
S2: KMP trick
只用找到从0开始的最长palindrome，再把剩下的字符reverse贴到前面即可。
比如abacd, aba是从0开始的最长palindrome, 只用把cd翻转为dc贴到前边得到dcabacd就是答案。
求从0开始的最长palindrome，trick是构造一个新string l = s + '#' + reverse(s),然后参考KMP算法中构造lps：longest proper prefix which is also suffix 的过程。（这里假设#不在原string中，#是为了在reverse(s)开始的时候将len清零）
string shortestPalindrome(string s) {
string rs(s.rbegin(), s.rend());
string l = s + '#' + rs;
vector<int> table(l.size(), 0);
int len = 0, i = 1, size = s.size();
while( i < l.size()){
if(l[i] == l[len]){
len++;
table[i] = len;
i++;
}
else if(len > 0){
len = table[len-1];//???
}
else{
table[i] = 0;
i++;
}
}
return l.substr(size+1, size-table[l.size()-1])+s;
}
266. Palindrome Permutation
Given a string, determine if a permutation of the string could form a palindrome.
For example,"code"-> False,"aab"-> True,"carerac"-> True.
S: bitset O(n)
只能有最多一个char出现奇数次，即出现在中间
bool canPermutePalindrome(string s) {
bitset<256> count;
for (char c : s) {
count.flip(c);
}
return count.count() < 2;
}
409. Longest Palindrome
Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.
This is case sensitive, for example"Aa"is not considered a palindrome here.
S: O(n)
最多只有一个char出现奇数次，其他出现奇数次的char都要减一
int longestPalindrome(string s) {
unordered_map<char, int> count;
for (char c : s) count[c]++;
int len = 0;
bool hasOdd = false;
for (auto i : count) {
if (i.second & 1) {
hasOdd = true;
len += i.second - 1;
} else len += i.second;
}
return hasOdd? len + 1 : len;
}
336. Palindrome Pairs
Given a list ofuniquewords, find all pairs ofdistinctindices(i, j)in the given list, so that the concatenation of the two words, i.e.words[i] + words[j]is a palindrome.
Example 1:
Givenwords=["bat", "tab", "cat"]
Return[[0, 1], [1, 0]]
The palindromes are["battab", "tabbat"]
Example 2:
Givenwords=["abcd", "dcba", "lls", "s", "sssll"]
Return[[0, 1], [1, 0], [3, 2], [2, 4]]
The palindromes are["dcbaabcd", "abcddcba", "slls", "llssssll"]
S1: brutal force O(n^2)
S2: hash map O(n*k^2) n is the size of word list, k is the average size of each word
关键是如何快速找到匹配的word：
- 反转每个词语存入hash map作为key，value为index
- 将word拆分为 left | right 两部分，只需要找到candidate满足candidate = left且right为palindrome(left|right|candidate) 或者 candidate = right且left为palindrome(candidate|left|right) 注意当中间那部分为空时会出现重复，只计算一次
class Solution {
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
unordered_map<string, int> revMap;
vector<vector<int>> result;
for (int i = 0; i < words.size(); ++i) {
string s = words[i];
reverse(s.begin(), s.end());
revMap[s] = i;
}
for (int i = 0; i < words.size(); ++i) {
int n = words[i].size();
for (int j = 0; j <= n; ++j) {
string left = words[i].substr(0, j);
string right = words[i].substr(j, n - j);
if (revMap.find(left) != revMap.end() && revMap[left] != i &&isPal(right)) { //left|right|candidate
result.push_back(vector<int>{i, revMap[left]});
}
if (left.size() > 0 && revMap.find(right) != revMap.end() && revMap[right] != i
&& isPal(left)) { //candidate|left|right
result.push_back(vector<int>{revMap[right], i});
}
}
}
return result;
}
bool isPal(string s) {
int left = 0, right = s.size() - 1;
while (left < right) {
if (s[left++] != s[right--]) return false;
}
return true;
}
};