# 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 "";
    }
};