# 214.Shortest-Palindrome

## ้ข็ฎๅฐๅ

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"``````

## ไปฃ็ 

### Approach # Brute Force

Time complexity: O(n^2)

``````class Solution {
public String shortestPalindrome(String s) {
int n = s.length();
String reversed = new StringBuilder(s).reverse().toString();
int j = 0;
for (int i = 0; i < n; i++) {
if (s.substring(0, n-i) == reversed.substring(i)) {
return resersed.substring(0, i) + s;
}
}

return "";
}
}``````

### Approach #1 Two pointers and recursion

``````class Solution {
public String shortestPalindrome(String s) {
int n = s.length();
int i = 0;
for (int j = n - 1; j >= 0; j--) {
if (s[i] == s[j]) {
i++;
}
}
if (i == n)     return s;

String remain = s.substring(i);
String prefix = new StringBuilder(remain).reverse().toString();
String subfix = shortestPalindrome(s.substring(0, i)) + remain;
return prefix + subfix;
}
}``````

### Approach #3 KMP

https://leetcode.com/problems/shortest-palindrome/discuss/60113/Clean-KMP-solution-with-super-detailed-explanation

``````public class Solution {
public String shortestPalindrome(String s) {
String temp = s + "#" + new StringBuilder(s).reverse().toString();
int[] table = getTable(temp);

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

public int[] getTable(String s) {
int[] table = new int[s.length()];

int index = 0;
for (int i = 1; i < s.length(); ) {
if (s.charAt(index) == s.charAt(i)) {
table[i] = ++index;
i++;
} else {
if (index > 0) {
index = table[index-1];
} else {
index = 0;
i ++;
}
}
}
return table;
}
}``````

Last updated