問(wèn)題

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.

例子

Given "aacecaaa", return "aaacecaaa".
Given "abcd", return "dcbabcd".

分析

方法一

窮舉法，枚舉N種情況，判斷每種情況的字符串是不是回文字符串。

方法二

kmp算法

要點(diǎn)

kmp算法

時(shí)間復(fù)雜度

方法一

O(n^2)

方法二

O(n)

空間復(fù)雜度

方法一

O(1)

方法二

O(n)

代碼

方法一

class Solution {
public:
    string shortestPalindrome(string s) {
        if (isPalindrome(s)) return s;
        string res, tail;
        for (int i = s.size() - 1; i >= 1; i--) {
            tail += s[i];
            res = tail + s;
            if (isPalindrome(res)) return res;
        }
        return s;
    }
    
private:
    bool isPalindrome(const string &s) {
        for (int i = 0; i < s.size() / 2; i++)
            if (s[i] != s[s.size() - i - 1]) return false;
        return true;
    }
};

方法二

class Solution {
public:
    string shortestPalindrome(string s) {
        string rev_s = s;
        reverse(rev_s.begin(), rev_s.end());
        string l = s + "#" + rev_s;
        
        vector<int> p(l.size(), 0);
        for (int i = 1; i < l.size(); i++) {
            int j = p[i - 1];
            while (j > 0 && l[i] != l[j])
                j = p[j - 1];
            p[i] = (j += l[i] == l[j]);
        }
        
        return rev_s.substr(0, s.size() - p[l.size() - 1]) + s;
    }
};