This page explains Java solution to problem Shortest Palindrome
using KMP
algorithm.
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 2:Input: "aacecaaa"
Output: "aaacecaaa"
Input: "abcd"
Output: "dcbabcd"
package com.vc.hard;
class ShortestPalindrome {
public String shortestPalindrome(String s) {
String sNew = s + "#" + reverse(s);
int[] kmp = new int[sNew.length()];
int n = sNew.length();
int start = 0, end = 1;
while(end < n) {
if(sNew.charAt(start) == sNew.charAt(end)) {
kmp[end] = start + 1;
start++;
end++;
}
else {
if(start == 0) kmp[end++] = 0;
else start = kmp[start - 1];
}
}
return reverse(s.substring(kmp[n - 1])) + s;
}
private String reverse(String s) {
int start = 0, end = s.length() - 1;
char[] cArr = s.toCharArray();
while(start < end) {
char ch = s.charAt(start);
cArr[start] = cArr[end];
cArr[end] = ch;
start++;
end--;
}
return new String(cArr);
}
}
O(N) Where
N is total number of elements in an input String
O(N) Where
N is total number of elements in an input String