214. Shortest Palindrome.md

214. Shortest Palindrome

---

leetcode-cn Daily Challenge on August 29th, 2020.

---

Difficulty : Hard

Related Topics : String

---

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"

---

Solution

• mine
  • Java
    • Brute Force Runtime: 221 ms, faster than 28.71%, Memory Usage: 40.7 MB, less than 21.61% of Java online submissions

      // O(N^2)time
      // O(N)space
      public String shortestPalindrome(String s) {
          char[] arr = s.toCharArray();
          int l = 0 , r = arr.length - 1;
          int t = r;
          while(l < t){
              if(arr[l] != arr[t]){
                  l = 0;
                  r--;
                  t = r;
              }else{
                  l++;
                  t--;
              }
          }
          StringBuilder sb = new StringBuilder();
          for(int i = arr.length - 1; i > r; i--){
              sb.append(arr[i]);
          }
          sb.append(s);
          return sb.toString();
      }
      

    • KMP -- got form the discuss Runtime: 5 ms, faster than 91.02%, Memory Usage: 39.4 MB, less than 89.95% of Java online submissions

      public String shortestPalindrome(String s) {
          String temp = s + "#" + new StringBuilder(s).reverse();
          int[] table = getTable(temp.toCharArray());
          return new StringBuilder(s.substring(table[table.length - 1])).reverse().toString() + s;
      }
      
      int[] getTable(char[] arr) {
          int[] table = new int[arr.length];
          //index mean in range [0, j], [0,index] and [j - index, j] is the same
          int index = 0;
          for (int i = 1; i < arr.length; i++) {
              if (arr[index] == arr[i]) {
                  table[i] = table[i - 1] + 1;
                  index++;
                  //or index++; table[i] = index;
                  //or table[i] = ++index;
              } else {
                  index = table[i - 1];
                  while (index > 0 && arr[index] != arr[i]) {
                      index = table[index - 1];
                  }
                  if (arr[index] == arr[i]) {
                      index++;
                  }
                  table[i] = index;
              }
          }
          return table;
      }
      

---

• the most votes

• KMP Runtime: 9 ms, faster than 65.37%, Memory Usage: 39.3 MB, less than 93.99% of Java online submissions

  // O(N)time
  // O(N)space
  public String shortestPalindrome(String s) {
      String temp = s + "#" + new StringBuilder(s).reverse().toString();
      int[] table = getTable(temp);
      //get the maximum palindrome part in s starts from 0
      return new StringBuilder(s.substring(table[table.length - 1])).reverse().toString() + s;
  }
  
  public int[] getTable(String s){
      //get lookup table
      int[] table = new int[s.length()];
      //pointer that points to matched char in prefix part
      int index = 0;
      //skip index 0, we will not match a string with itself
      for(int i = 1; i < s.length(); i++){
          if(s.charAt(index) == s.charAt(i)){
              //we can extend match in prefix and postfix
              table[i] = table[i-1] + 1;
              index ++;
          }else{
              //match failed, we try to match a shorter substring
  
              //by assigning index to table[i-1], we will shorten the match string length, and jump to the
              //prefix part that we used to match postfix ended at i - 1
              index = table[i-1];
  
              while(index > 0 && s.charAt(index) != s.charAt(i)){
                  //we will try to shorten the match string length until we revert to the beginning of match (index 1)
                  index = table[index-1];
              }
  
              //when we are here may either found a match char or we reach the boundary and still no luck
              //so we need check char match
              if(s.charAt(index) == s.charAt(i)){
                  //if match, then extend one char
                  index ++ ;
              }
              table[i] = index;
          }
      }
      return table;
  }
  

---

• leetcode solution

• String Hash Runtime: 2 ms, faster than 97.04%, Memory Usage: 39.2 MB, less than 97.43% of Java online submissions

  // O(N)time
  // O(1)space
  public String shortestPalindrome(String s) {
      int n = s.length();
      int base = 131, mod = 1000000007;
      int left = 0, right = 0, mul = 1;
      int best = -1;
      for (int i = 0; i < n; ++i) {
          left = (int) (((long) left * base + s.charAt(i)) % mod);
          right = (int) ((right + (long) mul * s.charAt(i)) % mod);
          if (left == right) {
              best = i;
          }
          mul = (int) ((long) mul * base % mod);
      }
      String add = (best == n - 1 ? "" : s.substring(best + 1));
      StringBuffer ans = new StringBuffer(add).reverse();
      ans.append(s);
      return ans.toString();
  }
  

• KMP Runtime: 3 ms, faster than 94.07%, Memory Usage: 39.1 MB, less than 97.89% of Java online submissions

  // O(N)time
  // O(N)space
  public String shortestPalindrome(String s) {
      int n = s.length();
      int[] fail = new int[n];
      Arrays.fill(fail, -1);
      for (int i = 1; i < n; ++i) {
          int j = fail[i - 1];
          while (j != -1 && s.charAt(j + 1) != s.charAt(i)) {
              j = fail[j];
          }
          if (s.charAt(j + 1) == s.charAt(i)) {
              fail[i] = j + 1;
          }
      }
      int best = -1;
      for (int i = n - 1; i >= 0; --i) {
          while (best != -1 && s.charAt(best + 1) != s.charAt(i)) {
              best = fail[best];
          }
          if (s.charAt(best + 1) == s.charAt(i)) {
              ++best;
          }
      }
      String add = (best == n - 1 ? "" : s.substring(best + 1));
      StringBuffer ans = new StringBuffer(add).reverse();
      ans.append(s);
      return ans.toString();
  }
  

---