You are given a string s. You can convert s to a palindrome by adding characters in front of it.
Return the shortest palindrome you can find by performing this transformation.
Example 1:
Input: s = "aacecaaa" Output: "aaacecaaa"
Example 2:
Input: s = "abcd" Output: "dcbabcd"
Constraints:
0 <= s.length <= 5 * 104s consists of lowercase English letters only.class Solution {
public String shortestPalindrome(String s) {
int n = s.length();
for (int i = n; i > 0; i--) {
String x = s.substring(0, i);
if (isPalindrome(x)) {
// System.out.println(x);
StringBuilder sb = new StringBuilder(s.substring(i));
sb.reverse();
sb.append(s);
return sb.toString();
}
}
return s;
}
private boolean isPalindrome(String s) {
int sz = s.length();
for (int lt = 0, rt = sz - 1; lt < rt; lt++, rt--)
if (s.charAt(lt) != s.charAt(rt))
return false;
return true;
}
}