public String shortestPalindrome(String s) { int len = s.length(); if (len <= 1) { return s; } int mid = (len - 1) / 2; String rst = null; for (int i = mid; i >= 0; i--) { if (s.charAt(i) == s.charAt(i + 1)) { if ((rst = getShortest(s, i, i + 1)) != null) { break; } } if ((rst = getShortest(s, i, i)) != null) { break; } } return rst; } private String getShortest(String s, int l, int r) { int i = 1; while (l - i >= 0 && r + i < s.length() && s.charAt(l - i) == s.charAt(r + i)) { i++; } if (l - i >= 0) { return null; } String prefix = new StringBuilder(s.substring(r + i)).reverse().toString(); return prefix + s; }
Here is the KMP solution.
public String shortestPalindrome(String s) { if (s == null || s.length() <= 1) return s; String reverse = new StringBuilder(s).reverse().toString(); int longest = findPMT(s + "#" + reverse); return reverse.substring(0, reverse.length() - longest) + s; } private int findPMT(String ptrn) { int ptrnLen = ptrn.length(); //partial match table int[] PMT = new int[ptrnLen + 1]; PMT[0] = -1; PMT[1] = 0; for (int i = 2; i <= ptrnLen; i++) { int j = PMT[i - 1]; while(j >= 0 && ptrn.charAt(j) != ptrn.charAt(i - 1)) { j = PMT[j]; } PMT[i] = j < 0 ? 0 : j + 1; } return PMT[ptrnLen]; }
No comments:
Post a Comment