214.Shortest-Palindrome

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

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