214. Shortest Palindrome

 1 class Solution {
 2     int missingLen;// 咱们的目的是要补全回文; 举例 asdsafgh,其中 asdsa是回文,右边多出了fgh,我们需要把fgh反转填到左边就行了;fgh被称为missingLen=3;
 3     
 4     void validate(String s, int i,int j)
 5     {
 6         while(i>=0&&j<s.length()&&s.charAt(i)==s.charAt(j))
 7         {
 8             --i;
 9             ++j;
10         }
11         if(-1==i&&s.length()-j<missingLen)
12         {
13             missingLen=s.length()-j;
14         }
15     }
16     
17     public String shortestPalindrome(String s) {
18         missingLen=s.length()-1;
19         for(int i=0;i<=s.length()/2;++i)
20         {
21             validate(s,i,i);
22             validate(s,i,i+1);
23         }
24         if(missingLen>0)
25         {
26             return new StringBuilder(s.substring(s.length()-missingLen)).reverse().append(s).toString();
27         }
28         return s;
29     }
30 }

这题目标的是hard难度,如果你做过回文题目, 这题算不上hard难度我想.

不需要什么搜索,dp,递归. 普通解法就可以accepted.