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"

// Recursion
string shortestPalindrome(string s) { // time: O(n^2); space: O(n)
    int i = 0, n = s.length();
    for (int j = n - 1; j >= 0; --j) {
        if (s[i] == s[j]) ++i;
    }
    if (i == n) return s;
    string rem = s.substr(i);
    reverse(rem.begin(), rem.end());
    return rem + shortestPalindrome(s.substr(0, i)) + s.substr(i);
}