# 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.

For example:

Given aacecaaa, return aaacecaaa.

Given abcd, return dcbabcd.

## Solution

We can solve this problem by using one of the methods which is used to solve the longest palindrome substring problem.

Specifically, we can start from the center and scan two sides. If read the left boundary, then the shortest palindrome is identified.

tips: 1. 中轴字符选从中间开始,这样找到的即为最短的. 2. 中轴字符可能为一个, 也可能为两个.

## Code

``````public class Solution {
public String shortestPalindrome(String s) {
if(s.length()<=1 ) return s;
int center = (s.length()-1)/2;
String res="";
for(int i=center; i>=0; i--) {
if(s.charAt(i) == s.charAt(i+1)) {
if( (res = check1(s, i, i+1)) !=null) return res;
}
if( (res = check1(s, i, i)) !=null) return res;

}
return res;
}
//aabaac
private String check1(String s, int l, int r) {
int i=1;
for(; l-i>=0 && r+i<s.length(); i++) {
if(s.charAt(l-i) != s.charAt(r+i) ) break;
}

if(l-i>=0) return null;
StringBuilder sb = new StringBuilder(s.substring(r+i));
sb.reverse();
return sb+s;
}
}
``````