214.Shortest-Palindrome

214. Shortest Palindrome

题目地址

https://leetcode.com/problems/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"

代码

Approach # Brute Force

Time complexity: O(n^2)

class Solution {
  public String shortestPalindrome(String s) {
    int n = s.length();
    String reversed = new StringBuilder(s).reverse().toString();
    int j = 0;
    for (int i = 0; i < n; i++) {
      if (s.substring(0, n-i) == reversed.substring(i)) {
        return resersed.substring(0, i) + s;
      }
    }

    return "";
  }
}

Approach #1 Two pointers and recursion

class Solution {
  public String shortestPalindrome(String s) {
        int n = s.length();
    int i = 0;
    for (int j = n - 1; j >= 0; j--) {
      if (s[i] == s[j]) {
        i++;
      }
    }
    if (i == n)     return s;

    String remain = s.substring(i);
    String prefix = new StringBuilder(remain).reverse().toString();
    String subfix = shortestPalindrome(s.substring(0, i)) + remain;
    return prefix + subfix;
  }
}

Approach #3 KMP

https://leetcode.com/problems/shortest-palindrome/discuss/60113/Clean-KMP-solution-with-super-detailed-explanation

public class Solution {
  public String shortestPalindrome(String s) {
    String temp = s + "#" + new StringBuilder(s).reverse().toString();
    int[] table = getTable(temp);

    return new StringBuilder(s.substring(table[table.length - 1])).reverse().toString() + s;
  }

  public int[] getTable(String s) {
    int[] table = new int[s.length()];

    int index = 0;
    for (int i = 1; i < s.length(); ) {
        if (s.charAt(index) == s.charAt(i)) {
            table[i] = ++index;
            i++;
        } else {
            if (index > 0) {
                index = table[index-1];
            } else {
                index = 0;
                i ++;
            }
        }
    }
    return table;
  }
}