leetcode 214 Shortest Palindrome
z
 2019-04-02 11:05:33  

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:

1
2
Input: "aacecaaa"
Output: "aaacecaaa"

Example 2:

1
2
Input: "abcd"
Output: "dcbabcd"
  • 对于任意一个S，我们需要尽可能的找到一个S[0:i]是一个回文，这样的话，S[0:i]可以保持不变，然后把S[i：i-1] reverse后放在最前面，使之能够成为满足要求的最短的回文。
  • 如何在S中尽可能的找到S[0：i]是一个回文呢？
    • 对于一个回文，最终重要的性质是S[i] = S[n-i]
    • 如果i在S中从左往右遍历，j在S中从右往左遍历，如果S[i] == S[j]，i++，j保持- -, 这样一来，如果S[0，somewhere]是一个回文的话，i肯定在somewhere的右边。也就是说S[0：i]肯定包含这个要求的回文prefix。那么S[i:-1]就是肯定需要进行转置后放到S前面的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public String shortestPalindrome(String s) {
        int left = 0;
        for (int right = s.length()-1; right>=0; right--) {
            if (s.charAt(left) == s.charAt(right)) {
                left ++;
            }
        }
        if (left == s.length())
            return s;
        String prefix = s.substring(0, left);
        String suffix = s.substring(left);
        return new StringBuilder(suffix).reverse().toString() + shortestPalindrome(prefix) + suffix;
    }
}