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.
For example:
Given "aacecaaa", return "aaacecaaa".
Given "abcd", return "dcbabcd".
Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases. Thanks to @Freezen for additional test cases.
Solution
Brute-force, time O(n ^ 2), space O(n)
Compare prefix of s with suffix of reversed s.
class Solution {
public String shortestPalindrome(String s) {
String reverse = reverse(s);
int len = s.length();
int i = len;
while (i > 0 && !s.substring(0, i).equals(reverse.substring(len - i))) {
--i;
}
return reverse.substring(0, len - i) + s;
}
public String reverse(String s) {
StringBuilder sb = new StringBuilder();
sb.append(s).reverse();
return sb.toString();
}
}
KMP, time O(n), space?
To be added.
