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.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases. Thanks to @Freezen for additional test cases.

inverse the input string.

check if inverse string == input string, if they are equal, return input string.

else move inverse string to left by one step. check if the overlapping part of inverse string and input string are equal.

if equal, merge the two string and return it as result.

else go on to move the inverse string to left by one step, continue.

O(n^2). The inner loop is the compare of two strings.

class Solution {
public:
    string shortestPalindrome(string s) {
        string inverse, ans;
        int len = s.size();
        if(s.size() == 0) return ans;
        for(int i = s.size() - 1; i >= 0; --i){
            inverse.push_back(s[i]);
        }
        for(int i = 0; i < s.size(); i++){
            if(inverse.substr(i, len - i) == s.substr(0, len - i)){
                ans = inverse;
                ans.append(s.substr(len - i, i));
                return ans;
            }    
        }
        ans = inverse;
        ans.append(s);
        return ans;
    }
};