# 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:

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.

reversed:  d a
s:           a d


Another example, “aacecaaa”

• i will stop at last ‘a’, i=7
• “a”+dfs(“aacecaa)+”a”

Java