# 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.
Example 1:
Input: "aacecaaa"
Output: "aaacecaaa"
Example 2:
Input: "abcd"
Output: "dcbabcd"
# Solution
Approach 1: Start from the middle bit and then expand through both directions
Approach 2: (Memory Limit Exceeded) Reversion - brute force.
# Code (Python)
Approach 1:
Approach 2:
# Code (C++)
Approach 1:
class Solution {
public:
string shortestPalindrome(string s) {
int n = s.size();
if (n <= 1)
return s;
int minFront = n;
for (int i = (n-1)/2; i >= 0; --i)
{
if (n-i-i-1 >= minFront)
continue;
int head = i-1;
int tail = i+1;
while (head >= 0)
{
if (s[head] != s[tail])
break;
head--;
tail++;
}
if (head < 0)
minFront = std::min(minFront, n - tail);
}
for (int i = n/2-1; i >= 0; --i)
{
if (s[i] != s[i+1] || n-i-i-2 >= minFront)
continue;
int head = i-1;
int tail = i+2;
while (head >= 0)
{
if (s[head] != s[tail])
break;
head--;
tail++;
}
if (head < 0)
minFront = std::min(minFront, n - tail);
}
ostringstream oss;
for (int i = 1; i <= minFront; ++i)
{
oss << s[n-i];
}
oss << s;
return oss.str();
}
};
Approach 2:
// Memory Limit Exceeded.
// Brute force.
class Solution {
public:
string shortestPalindrome(string s) {
int n = s.size();
if (n <= 1)
return s;
string rev = s;
std::reverse(rev.begin(), rev.end());
for (int i = 0; i < n; ++i)
{
if (s.substr(0, n-i) == rev.substr(i))
return rev.substr(0, i) + s;
}
return "";
}
};