38 lines
876 B
Java
38 lines
876 B
Java
class Solution {
|
|
private String convert(String s) {
|
|
var reversed = new StringBuilder(s).reverse();
|
|
|
|
var combined = new StringBuilder(s);
|
|
combined.append('#');
|
|
combined.append(reversed);
|
|
|
|
return combined.toString();
|
|
}
|
|
|
|
private int[] makePrefixTable(String s) {
|
|
var result = new int[s.length()];
|
|
|
|
var length = 0;
|
|
for (int i = 1; i < s.length(); ++i) {
|
|
while (length > 0 && s.charAt(i) != s.charAt(length)) {
|
|
length = result[length - 1];
|
|
}
|
|
|
|
if (s.charAt(i) == s.charAt(length)) {
|
|
++length;
|
|
}
|
|
|
|
result[i] = length;
|
|
}
|
|
|
|
return result;
|
|
}
|
|
|
|
public String shortestPalindrome(String s) {
|
|
var prefix = makePrefixTable(convert(s));
|
|
var length = prefix[prefix.length - 1];
|
|
|
|
var suffix = new StringBuilder(s.substring(length)).reverse();
|
|
return suffix.append(s).toString();
|
|
}
|
|
}
|