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;

        }
    }
}

// OJ: https://leetcode.com/problems/shortest-palindrome/
// Time: O(N)
// Space: O(1) ignoring the space taken by the answer
class Solution {
public:
    string shortestPalindrome(string s) {
        unsigned d = 16777619, h = 0, rh = 0, p = 1, maxLen = 0;
        for (int i = 0; i < s.size(); ++i) {
            h = h * d + s[i] - 'a';
            rh += (s[i] - 'a') * p;
            p *= d;
            if (h == rh) maxLen = i + 1;
        }
        return string(rbegin(s), rbegin(s) + s.size() - maxLen) + s;
    }
};

class Solution(object):
  # brutal force TLE
  def _shortestPalindrome(self, s):
    """
    :type s: str
    :rtype: str
    """

    def isPal(cand):
      start, end = 0, len(cand) - 1
      while start < end:
        if cand[start] != cand[end]:
          return False
        start += 1
        end -= 1
      return True

    n = len(s)
    ans = s[::-1] + s
    ansLen = 2 * len(s)
    for i in reversed(range(0, len(s) + 1)):
      newPal = s[i:][::-1] + s
      if isPal(newPal) and n + len(s) - i < ansLen:
        ansLen = n + len(s) - i
        ans = newPal
    return ans

  def shortestPalindrome(self, s):
    r = s[::-1]
    for i in range(len(s) + 1):
      if s.startswith(r[i:]):
        return r[:i] + s

214 - Shortest Palindrome

Question

Algorithm

Code

All Problems

All Solutions