Question
Formatted question description: https://leetcode.ca/all/214.html
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"
Algorithm
- The worst case is that there are no identical characters in s, so the minimum number of characters that need to be added is s.size()-1.
- The string in the first example contains a palindrome string, just add it in front Just one character
First flip the string s to be processed to get t, then compare the original string s with the flipped string t, starting from the first character and compare one by one,
- If they are equal, it means that s itself is a palindrome. You don’t need to add any characters, just return directly;
- If they are not equal, remove the last bit from s, remove the first bit from t, and continue to compare, and so on until there is an equality or the loop ends
This will concatenate the two strings in the correct position.
Example:
worst case: “abcda”+”adcba”
reversed: a b c d a
s: a d c b a
try to move both to the center, to find possible overlap, then one char less, by saving an “a”
reversed: a b c d a
s: a d c b a
move more, “da”-“ad” overlap, and rest part is palindrome, “abc” vs “cba”
reversed: a b c d a
s: a d c b a
so, put “da”-“ad” to next recursion
reversed: d a
s: a d
move one more, and bingo got the final result.
- “abc”+dfs()+”cba” => “abc”+”dad”+”cba”
reversed: d a s: a d
Another example, “aacecaaa”
- i will stop at last ‘a’, i=7
- “a”+dfs(“aacecaa)+”a”
Code
Java
public class Shortest_Palindrome {
public class Solution {
public String shortestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
int i = 0, n = s.length();
for (int j = n - 1; j >= 0; --j) { // @note: j will cross i, eg. making i=2 for "adcba"
if (s.charAt(i) == s.charAt(j)) {
++i;
}
}
// now [0, i) is a possible palindrome, but need extra check
if (i == n) {
return s;
}
String remaining = s.substring(i); // need to add reverse part of it
String rem_rev = new StringBuilder(remaining).reverse().toString();
return rem_rev + shortestPalindrome(s.substring(0, i)) + remaining;
}
}
}