0200 - 0299
0214 - Shortest Palindrome (Hard)
Problem Link
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^4sconsists 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 and iterate . If there is a that can satisfy , then the answer would be + where is the first characters of .
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 "";
}
};