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"
class Solution { public String shortestPalindrome(String s) { if(s == null || s.length() == 0) return s; int right = 1; for(int i = 2; i <= s.length(); i++){ if(helper(s.substring(0, i))) right = i; } if(right == s.length()) return s; String front = s.substring(0, right); String back = s.substring(right); StringBuilder sb = new StringBuilder(back); String nback = sb.reverse().toString(); return nback+front+back; } public boolean helper(String s){ int left = 0, right = s.length() - 1; while(left < right){ if(s.charAt(left) != s.charAt(right)) return false; left++; right--; } return true; } }
1. brute force
因为只能从front插入，所以先找从前往后最长palindrome，然后剩下的reverse后加到前面
class Solution { public String shortestPalindrome(String s) { int i = 0, end = s.length() - 1, j = end; char chs[] = s.toCharArray(); while(i < j) { if (chs[i] == chs[j]) { i++; j--; } else { i = 0; end--; j = end; } } return new StringBuilder(s.substring(end+1)).reverse().toString() + s; } }
原文：https://www.cnblogs.com/wentiliangkaihua/p/13171402.html