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  for adding this problem and creating all test cases. Thanks to  for additional test cases.

 

这题比较直观的解法是，寻找s中以s[0]为起始的最长回文子串pres（因此是从s的尾部往前遍历，判断是回文即返回），

即后续部分为sufs，然后只需要在s之前补全reverse_sufs的逆转即可。

这样的话reverse_sufs与sufs对称，pres自己与自己对称，肯定是最短回文串。

最坏复杂度为O(n^2)，n为s中字符个数。

然而被某个奇葩的测试用例超时了。

先贴出来吧，个人认为面试的十分钟内能写出这个已经可以pass了。

后文再贴标准做法。

class Solution {public:    string shortestPalindrome(string s) {        if(s == "")            return s;        int i = s.size()-1;        while(i >= 0)        {            // spre is s[0,...,i]            string spre = s.substr(0, i+1);            if(isPalin(spre))                break;            i --;        }        string pre = s.substr(i+1);        reverse(pre.begin(), pre.end());        return pre + s;    }    bool isPalin(string s)    {        for(int i = 0, j = s.size()-1; i < j; i ++, j --)        {            if(s[i] != s[j])                return false;        }        return true;    }};

 

首先确认一点基本知识，如果某个字符串str是回文的，那么str == reverse(str)

因此，将s逆转之后拼接在s后面，即news=s+reverse(s)，该新字符串news首尾相同的部分，即为s中以s[0]为起始的最长回文子串pres

只不过这里我不用上述的遍历来做，而用类似KMP算法求next数组来做。

在KMP算法中求next数组就是s自我匹配的过程，next[i]的值就表示s[i]之前有几个元素是与s开头元素相同的。

因此，next[news.size()]的值就表示news中首尾相同的部分的长度。接下来就好做了。

注意：当next[news.size()]的值大于s.size()时，说明重复部分贯穿了s与reverse(s)，应该修正为next[news.size()]+1-s.size()

class Solution {public:    string shortestPalindrome(string s) {        if(s == "")            return s;        string s2 = s;        reverse(s2.begin(), s2.end());        string news = s + s2;        int n = news.size();        vector
     
       next(n+1);        buildNext(news, next, n);        if(next[n] > s.size())            next[n] = next[n] + 1 - s.size();        string pres = s.substr(next[n]);        reverse(pres.begin(), pres.end());        return pres + s;    }    void buildNext(string& s, vector
      
       & next, int n)    {        int k = -1;        int j = 0;        next[0] = -1;        while(j < n)        {            if(k == -1 || s[j] == s[k])            {                k ++;                j ++;                next[j] = k;            }            else            {                k = next[k];            }        }    }};