LeetCode - Shortest Palindrome
Problem description
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:
1
2
Input: "aacecaaa"
Output: "aaacecaaa"
Example 2:
1
2
Input: "abcd"
Output: "dcbabcd"
Analysis
The first thought is to reverse the input string and find duplicates from last.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public String shortestPalindrome(String s) {
StringBuilder sb = new StringBuilder(s);
sb.reverse();
String reverse = sb.toString();
if (s.equals(reverse)){
return s;
}
int minIndex = s.length();
for (int i = 1; i < s.length(); i++){
int index = s.indexOf(reverse.substring(s.length() - i));
if (index == 0 || index == 1){
minIndex = Math.min(minIndex, s.length() - i);
}
}
return reverse.substring(0, minIndex) + s;
}
}
And this will TLE since the TC is O(n*n).
A better solution is to use KMP.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public String shortestPalindrome(String s) {
if(s == null || s.length() == 0) return s;
String revStr = new StringBuilder(s).reverse().toString();
int[] pi = findPi(s + revStr);
int LEN = pi.length, len = s.length();
int removed = pi[LEN - 1];
while(removed > len) {
removed = pi[removed - 1];
}
return revStr.substring(0, len - removed) + s;
}
int[] findPi(String str) {
int len = str.length();
int[] pi = new int[len];
int i = 1, j = 1;
while(i < len) {
j = pi[i - 1];
while(j > 0 && str.charAt(j) != str.charAt(i)) {
j = pi[j - 1];
}
if(str.charAt(j) == str.charAt(i)) j++;
pi[i++] = j;
}
return pi;
}
}
What to improve
- string needs summarize