# 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 = -1;
next = 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 == 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 = -1;
next = 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=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) {

continue;
}

if (ws == 2) {
if (sub.charAt(0) == sub.charAt(1)) {
} else {
}

continue;
}

// for window size >= 3
String subsub = sub.substring(1, ws - 1);

// if the middle string is invalid
if (invalidPal.contains(subsub)) {

continue;
}

if (sub.charAt(0) != sub.charAt(ws - 1)) {

continue;
} else {

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;
}
}
``````