`

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

 

Solution 1:

public String shortestPalindrome(String s) {
    StringBuilder sb = new StringBuilder(s).reverse();
    for(int i=0; i<s.length(); i++) {
        if(s.startsWith(sb.substring(i))) {
            return sb.substring(0, i)+s;
        }
    }
    return s;
}

但是以上代码再跑很长的字符串时会超时,所以应该用KMP来解决。

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics