Shortest Palindrome Problem
Description
LeetCode Problem 214.
You are given a string s. You can convert s to a palindrome by adding characters in front of it.
Return the shortest palindrome you can find by performing this transformation.
Example 1:
1
2
Input: s = "aacecaaa"
Output: "aaacecaaa"
Example 2:
1
2
Input: s = "abcd"
Output: "dcbabcd"
Constraints:
- 0 <= s.length <= 5 * 10^4
- s consists of lowercase English letters only.
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
string shortestPalindrome(string s) {
int n = s.size();
int i = 0;
for (int j = n - 1; j >= 0; j--) {
if (s[i] == s[j])
i++;
}
if (i == n) {
return s;
}
string remain_rev = s.substr(i, n);
reverse(remain_rev.begin(), remain_rev.end());
return remain_rev + shortestPalindrome(s.substr(0, i)) + s.substr(i);
}
};