# 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.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

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

Solution: O(N^2)

find the longest palindrome string start from index 0

``````public String shortestPalindrome(String s) {
if (s == null || s.length() <= 1)
return s;

String result = null;

int len = s.length();
int mid = len / 2;

for (int i = mid; i >= 1; i--) {
if (s.charAt(i) == s.charAt(i - 1)) {
if ((result = scanFromCenter(s, i - 1, i)) != null)
return result;
} else {
if ((result = scanFromCenter(s, i - 1, i - 1)) != null)
return result;
}
}

return result;
}

private String scanFromCenter(String s, int l, int r) {
int i = 1;

//scan from center to both sides
for (; l - i >= 0; i++) {
if (s.charAt(l - i) != s.charAt(r + i))
break;
}

//if not end at the beginning of s, return null
if (l - i >= 0)
return null;

StringBuilder sb = new StringBuilder(s.substring(r + i));
sb.reverse();

return sb.append(s).toString();
}
``````

Solution: O(N) but not explanation

https://leetcode.com/discuss/51223/my-7-lines-recursive-java-solution

``````public class Solution {
public String shortestPalindrome(String s) {
int j = 0;

for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == s.charAt(j)) { j += 1; }
}

if (j == s.length()) { return s; }
String suffix = s.substring(j);
return new StringBuilder(suffix).reverse().toString() + shortestPalindrome(s.substring(0, j)) + suffix;
}
}
``````

Solution: KMP, O(N)

https://leetcode.com/discuss/52564/a-kmp-based-java-solution-with-explanation

``````public class Solution {
public String shortestPalindrome(String s) {
if(s.length()<=1) return s;
String new_s = s+"#"+new StringBuilder(s).reverse().toString();
int[] position = new int[new_s.length()];

for(int i=1;i<position.length;i++)
{
int pre_pos = position[i-1];
while(pre_pos>0 && new_s.charAt(pre_pos)!=new_s.charAt(i))
pre_pos = position[pre_pos-1];
position[i] = pre_pos+((new_s.charAt(pre_pos)==new_s.charAt(i))?1:0);
}

return new StringBuilder(s.substring(position[position.length-1])).reverse().toString()+s;
}
}
``````