214. Shortest Palindrome (Hard)
https://leetcode.com/problems/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.
Example 1:
Input:"aacecaaa"
Output:"aaacecaaa"
Example 2:
Input:"abcd"
Output:"dcbabcd"
Solutions
class Solution {
private int match(String s, String p) {
char[] str = s.toCharArray();
char[] pattern = p.toCharArray();
int[] next = getNextArray2(pattern);
int strPtr = 0;
int patternPtr = 0;
while (strPtr > patternPtr) {
if (patternPtr == -1) {
patternPtr++;
strPtr++;
} else if (pattern[patternPtr] == str[strPtr]) {
patternPtr++;
strPtr++;
} else {
patternPtr = next[patternPtr];
}
}
if (patternPtr == p.length()) {
return strPtr - p.length();
}
return -1;
}
public String shortestPalindrome(String s) {
if (s == null || s.length() <= 1) {
return s;
}
int len = s.length();
char[] str = s.toCharArray();
char[] pattern = s.toCharArray();
int[] next = getNextArray(pattern);
int strPtr = len - 1;
int patternPtr = 0;
while (strPtr > patternPtr) {
if (patternPtr == -1) {
patternPtr++;
strPtr--;
} else if (pattern[patternPtr] == str[strPtr]) {
patternPtr++;
strPtr--;
} else {
patternPtr = next[patternPtr];
}
}
int palLen = 0;
// if patternPtr == 0, palLen should be 1
if (strPtr == patternPtr) {
// patternPtr is index
palLen = (patternPtr + 1) * 2 - 1;
} else {
// patternPtr is index
palLen = patternPtr * 2;
}
String ans = s;
// FIXME Do not use following method that concatenate the chars which trigger time limit exceeding, use StringBuild instead.
// for (int i = palLen; i < len; i++) {
// ans = s.charAt(i) + ans;
// }
ans = new StringBuilder(s.substring(palLen)).reverse().toString() + ans;
return ans;
}
// Incorrect method
private int[] getNextArray(char[] pattern) {
int len = pattern.length;
int[] next = new int[len];
next[0] = -1;
next[1] = 0;
for (int i = 2; i < len; i++) {
int lastMatchedCount = next[i - 1];
if (pattern[lastMatchedCount] == pattern[i - 1]) {
next[i] = next[i - 1] + 1;
} else if (pattern[0] == pattern[i - 1]) {
next[i] = 1;
} else {
next[i] = 0;
}
}
return next;
}
// Correct method
public int[] getNextArray2(char[] pattern) {
int[] next = new int[pattern.length];
next[0] = -1;
next[1] = 0;
int matchedCount;
for (int j = 2; j < pattern.length; j++) {
// previously matched count
matchedCount = next[j - 1];
while (matchedCount != -1) {
// Standing at index j, if previous char pattern[j-1] matches the (matchedCount)th char, current next[j] increases
// And up till index j-1, next[j] chars matches
// matched chars pattern[0:matchedCount-1]
if (pattern[j - 1] == pattern[matchedCount]) {
next[j] = matchedCount + 1;
break;
}
// if not match, technically, we need to compare from the head, but we can take advantage of the previously
// computed offset information. Consequently, set matchedCount to the offset that pattern failed to match
// at (matchedCount)th char instead of starting over from the head. Take following pattern string as example,
// 9th char is 'd' which differs from 5th char 'f', but we don't have to search from 6th char, we can take
// advantage of next[4]=1, then compare 1th char 'd' with 9th char 'd'.
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
// [s, d, f, s, f, s, d, f, s, d, f]
// [-1,0, 0, 0, 1, 0, 1, 2, 3, 4, 2]
matchedCount = next[matchedCount];
next[j] = 0;
}
}
return next;
}
}
Incorrect Solutions
class Solution {
// FIXME Time limit exceeds. Actually the following idea is much more time consuming than the brute force.
// This problem is not that difficult, the trick is to find the max length palindrome
// starting from index 0
public String shortestPalindrome(String s) {
if (s == null || s.length() <= 1) {
return s;
}
// find the max length palindrome starting from index 0
int maxLen = 1;
if (s.charAt(0) == s.charAt(1)) {
maxLen = 2;
}
Set<String> validPal = new HashSet<>();
Set<String> invalidPal = new HashSet<>();
// ws is window size
for (int ws = 1; ws <= s.length(); ws++) {
for (int start = 0; start < s.length() - ws + 1; start++) {
String sub = s.substring(start, start + ws);
if (ws == 1) {
validPal.add(sub);
continue;
}
if (ws == 2) {
if (sub.charAt(0) == sub.charAt(1)) {
validPal.add(sub);
} else {
invalidPal.add(sub);
}
continue;
}
// for window size >= 3
String subsub = sub.substring(1, ws - 1);
// if the middle string is invalid
if (invalidPal.contains(subsub)) {
invalidPal.add(sub);
continue;
}
if (sub.charAt(0) != sub.charAt(ws - 1)) {
invalidPal.add(sub);
continue;
} else {
validPal.add(sub);
if (start == 0) {
maxLen = ws;
}
}
}
}
String ans = "";
String prefix = s.substring(maxLen);
for (int i = 0; i < prefix.length(); i++) {
ans = prefix.charAt(i) + ans;
}
ans += s;
return ans;
}
}