LeetCode [214] Shortest Palindrome

214. Shortest Palindrome

Hard

Given a string s, you can 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: s = "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: s = "abcd"
Output: "dcbabcd"

 

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of lowercase English letters only.

========

Alg1:

 s = aacecaaa   r = aaacecaa   l = aacecaaa#aaacecaa

0  1  2   3  4  5  6  7  8  9  0  1  2  3  4  5  6   ............... index i

a  a  c  e  c a  a  a  #  a  a a  c  e  c  a  a

0  1  0   0  0  1  2  2  0  1  2  2  3  4  5  6  7  ................vector p

|---------7---------|               |---------7---------|

• string[i, j] denotes the substring of string from i to j.
• p[i] is the length of the longest suffix of l[0, i] which is equal to the prefix of l[0, i]. eg., p[13] = 4 which means l[0, 3] = l[10, 13].
• The last element of p, p[16]=7, indicates the length the longest suffix of l equal to its prefix. ie., l[0, 6] = l[10, 16].
•  p[16] is also the length of longest suffix of r which is equal to a prefix of s. 
• Thus, the result is r[0, 0]+s. ie., "a"+"aacecaaa".
• To compute p:
• Note that a string itself is not considered as the prefix here; otherwise we would always have p[i]=i+1. Thus, p[0]=0;
• line 12: since j is the length of the longest suffix of l[0, i-1] equal to its prefix, l[0, j-1] = l[i-j, i-1]. 
• line 13-15: if l[i]!=l[j], according to KMP, the next number to be considered is the (p[j-1])-th number of l.
• line 16-18: if l[i]==l[j], it means  l[0, j] = l[i-j, i]. Thus, p[i] = j+1.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

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