Skip to main content

0214 - Shortest Palindrome (Hard)

https://leetcode.com/problems/shortest-palindrome/

Problem Statement​

You are given a string s. You can convert s to a palindrome by adding characters in front of it.

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 * 10^4
  • s consists of lowercase English letters only.

Approach 1: Z Algorithm​

We first concatenate the search pattern and given string with a character that is not in either strings, says $. Hence, we have k = s + $ + t. Then We built ZZ and iterate kk. If there is a ii that can satisfy Z[i]==n−iZ[i] == n - i, then the answer would be t′t'+ ss where t′t' is the first n−in - i characters of ss.

Written by @wingkwong
class Solution {
public:
    vector<int> z_function(string s) {
        int n = (int) s.length();
        vector<int> z(n);
        for (int i = 1, l = 0, r = 0; i < n; ++i) {
            if (i <= r)
                z[i] = min (r - i + 1, z[i - l]);
            while (i + z[i] < n && s[z[i]] == s[i + z[i]])
                ++z[i];
            if (i + z[i] - 1 > r)
                l = i, r = i + z[i] - 1;
        }
        return z;
    }
    
    string shortestPalindrome(string s) {
        string r(s);
        reverse(r.begin(), r.end());
        string k = s + "$" + r;
        vector<int> z = z_function(k);
        int n = k.size();
        for(int i = 0; i < n; i++) {
            if(z[i] == n - i) {
                string s2 = s.substr(n - i);
                reverse(s2.begin(), s2.end());
                return s2 + s;
            }
        }
        return "";
    }
};