问题
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.
例子
Given "aacecaaa", return "aaacecaaa".
Given "abcd", return "dcbabcd".
分析
方法一
穷举法，枚举N种情况，判断每种情况的字符串是不是回文字符串。
方法二
kmp算法
要点
kmp算法
时间复杂度
方法一
O(n^2)
方法二
O(n)
空间复杂度
方法一
O(1)
方法二
O(n)
代码
方法一
class Solution {
public:
string shortestPalindrome(string s) {
if (isPalindrome(s)) return s;
string res, tail;
for (int i = s.size() - 1; i >= 1; i--) {
tail += s[i];
res = tail + s;
if (isPalindrome(res)) return res;
}
return s;
}
private:
bool isPalindrome(const string &s) {
for (int i = 0; i < s.size() / 2; i++)
if (s[i] != s[s.size() - i - 1]) return false;
return true;
}
};
方法二
class Solution {
public:
string shortestPalindrome(string s) {
string rev_s = s;
reverse(rev_s.begin(), rev_s.end());
string l = s + "#" + rev_s;
vector<int> p(l.size(), 0);
for (int i = 1; i < l.size(); i++) {
int j = p[i - 1];
while (j > 0 && l[i] != l[j])
j = p[j - 1];
p[i] = (j += l[i] == l[j]);
}
return rev_s.substr(0, s.size() - p[l.size() - 1]) + s;
}
};
