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
    
    

All Problems

All Solutions