Java for LeetCode 214 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".

解题思路:

本题最简单的思路是从后往前判断子串是否是回文串,然后把后面的弄到前面即可,不过这样仅仅能擦边通过测试,最高效的当然是KMP算法了,

KMP可以参考Java for LeetCode 028 Implement strStr()

JAVA实现如下;

    public String shortestPalindrome(String s) {
for(int i=s.length();i>=1;i--)
if(isPalindrome(s.substring(0, i)))
return new StringBuilder(s.substring(i)).reverse()+s;
return "";
}
static boolean isPalindrome(String s){
int left=0,right=s.length()-1;
while(left<right)
if(s.charAt(left++)!=s.charAt(right--))
return false;
return true;
}
上一篇:Java for LeetCode 216 Combination Sum III


下一篇:Java for LeetCode 210 Course Schedule II