@@ -0,0 +1,1547 @@
+// Recursive solution (2 pointers) runs in O(n%5E2) time and O(n) space%0A// Solution is an adaptation of the official C++ solution.%0Aclass Solution %7B%0A  public String shortestPalindrome(String s) %7B%0A    int i = 0;%0A    for (int j = s.length() - 1; j %3E= 0; j--) %7B%0A      if (s.charAt(i) == s.charAt(j)) %7B%0A        ++i;%0A      %7D%0A    %7D%0A    if (i == s.length()) return s;%0A    String rem = reverse(s.substring(i, s.length()));%0A    return rem + shortestPalindrome(s.substring(0, i)) + s.substring(i);%0A  %7D%0A%0A  private String reverse(String s) %7B%0A    StringBuilder sb = new StringBuilder();%0A    for (int i = s.length() - 1; i %3E= 0; i--) %7B%0A      sb.append(s.charAt(i));%0A    %7D%0A    return sb.toString();%0A  %7D%0A%7D%0A%0A// KMP solution runs in O(n) and uses O(n) space.%0A// Solution is an adaptation of the official C++ solution.%0A// Idea is using Knuth%E2%80%93Morris%E2%80%93Pratt algorithm, specifically lookup table.%0Aclass Solution %7B%0A  public String shortestPalindrome(String s) %7B%0A    String rev = reverse(s);%0A    String snew = s + %22#%22 + rev;%0A    int%5B%5D f = new int%5Bsnew.length()%5D;%0A    for (int i = 1; i %3C f.length; i++) %7B%0A      int t = f%5Bi - 1%5D;%0A      while (t %3E 0 && snew.charAt(t) != snew.charAt(i)) %7B%0A        t = f%5Bt - 1%5D;%0A      %7D%0A      if (snew.charAt(t) == snew.charAt(i)) %7B%0A        ++t;%0A      %7D%0A      f%5Bi%5D = t;%0A    %7D%0A    return rev.substring(0, s.length() - f%5Bsnew.length() - 1%5D) + s;%0A  %7D%0A%0A  private String reverse(String s) %7B%0A    StringBuilder sb = new StringBuilder();%0A    for (int i = s.length() - 1; i %3E= 0; i--) %7B%0A      sb.append(s.charAt(i));%0A    %7D%0A    return sb.toString();%0A  %7D%0A%7D%0A

add solution