Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/214.html

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 * 104
  • s consists of lowercase English letters only.

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

  • 
    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;
    
            }
        }
    }
    
    ############
    
    class Solution {
        public String shortestPalindrome(String s) {
            int base = 131;
            int mul = 1;
            int mod = (int) 1e9 + 7;
            int prefix = 0, suffix = 0;
            int idx = 0;
            int n = s.length();
            for (int i = 0; i < n; ++i) {
                int t = s.charAt(i) - 'a' + 1;
                prefix = (int) (((long) prefix * base + t) % mod);
                suffix = (int) ((suffix + (long) t * mul) % mod);
                mul = (int) (((long) mul * base) % mod);
                if (prefix == suffix) {
                    idx = i + 1;
                }
            }
            if (idx == n) {
                return s;
            }
            return new StringBuilder(s.substring(idx)).reverse().toString() + s;
        }
    }
    
  • // 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;
        }
    };
    
  • '''
    reversed(): returns a reverse iterator
    
    >>> s = "aabbcc"
    >>> reversed(s)
    <reversed object at 0x108384a60>
    >>> ''.join(reversed(s))
    'ccbbaa'
    
    
    >>> s = "aabbcc"
    >>> s[::-1]
    'ccbbaa'
    '''
    class Solution:
        def shortestPalindrome(self, s: str) -> str:
            if not s:
                return ""
    
            i, n = 0, len(s)
            for j in range(n - 1, -1, -1):
                if s[i] == s[j]:
                    i += 1
    
            if i == n:
                return s
    
            remaining = s[i:]
            rem_rev = remaining[::-1]
            return rem_rev + self.shortestPalindrome(s[:i]) + remaining
    
    
    class Solution:
        def shortestPalindrome(self, s: str) -> str:
            base = 131
            mod = 10**9 + 7
            n = len(s)
            prefix = suffix = 0
            mul = 1
            idx = 0
            for i, c in enumerate(s):
                prefix = (prefix * base + (ord(c) - ord('a') + 1)) % mod
                suffix = (suffix + (ord(c) - ord('a') + 1) * mul) % mod
                mul = (mul * base) % mod
                if prefix == suffix:
                    idx = i + 1
            return s if idx == n else s[idx:][::-1] + 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
    
    
  • func shortestPalindrome(s string) string {
    	n := len(s)
    	base, mod := 131, int(1e9)+7
    	prefix, suffix, mul := 0, 0, 1
    	idx := 0
    	for i, c := range s {
    		t := int(c-'a') + 1
    		prefix = (prefix*base + t) % mod
    		suffix = (suffix + t*mul) % mod
    		mul = (mul * base) % mod
    		if prefix == suffix {
    			idx = i + 1
    		}
    	}
    	if idx == n {
    		return s
    	}
    	x := []byte(s[idx:])
    	for i, j := 0, len(x)-1; i < j; i, j = i+1, j-1 {
    		x[i], x[j] = x[j], x[i]
    	}
    	return string(x) + s
    }
    
  • // https://leetcode.com/problems/shortest-palindrome/
    
    using System.Text;
    
    public partial class Solution
    {
        public string ShortestPalindrome(string s)
        {
            for (var i = s.Length - 1; i >= 0; --i)
            {
                var k = i;
                var j = 0;
                while (j < k)
                {
                    if (s[j] == s[k])
                    {
                        ++j;
                        --k;
                    }
                    else
                    {
                        break;
                    }
                }
                if (j >= k)
                {
                    var sb = new StringBuilder(s.Length * 2 - i - 1);
                    for (var l = s.Length - 1; l >= i + 1; --l)
                    {
                        sb.Append(s[l]);
                    }
                    sb.Append(s);
                    return sb.ToString();
                }
            }
    
            return string.Empty;
        }
    }
    

All Problems

All Solutions