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.

Example 1:

Input: "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: "abcd"
Output: "dcbabcd"

Approach #1 Brute force [Accepted]

Intuition

According to the question, we are allowed to insert the characters only at the beginning of the string. Hence, we can find the largest segment from the beginning that is a palindrome, and we can then easily reverse the remaining segment and append to the beginning. This must be the required answer as no shorter palindrome could be found than this by just appending at the beginning.

For example: Take the string \text{"abcbabcab"}"abcbabcab". Here, the largest palindrome segment from beginning is \text{"abcba"}"abcba", and the remaining segment is \text{"bcab"}"bcab". Hence the required string is reverse of \text{"bcab"}"bcab"( = \text{"bacb"}"bacb") + original string( = \text{"abcbabcab"}"abcbabcab") = \text{"bacbabcbabcab"}"bacbabcbabcab".

Algorithm

Create the reverse of the original string ss, say rev. This is used for comparison to find the largest palindrome segment from the front.

Iterate over the variable ii from 0 to the \text{size(s)}-1size(s)−1:

If s[0:n-i] == rev[i:]s[0:n−i]==rev[i:] (i.e. substring of ss from 00 to n-in−i is equal to the substring of \text{rev}rev from ii to the end of string). This essentially means that that substring from 00 to n-in−i is a palindrome, as \text{rev}rev is the reverse of ss.

Since, we find the larger palindromes first, we can return reverse of largest palindrome + ss as soon as we get it.

public class Solution {

    public String shortestPalindrome(String s) {

        int j = 0;

        for (int i = s.length() - 1; i >= 0; i--) {//找到第一个使他不回文的位置

           if (s.charAt(i) == s.charAt(j)) { 

               j += 1; 

           }

        }

        if (j == s.length()) {  //本身是回文

            return s; 

        }

        String suffix = s.substring(j); // 后缀不能够匹配的字符串

        String prefix = new StringBuilder(suffix).reverse().toString(); // 前面补充prefix让他和suffix回文匹配

        String mid = shortestPalindrome(s.substring(0, j)); //递归调用找 [0,j]要最少可以补充多少个字符让他回文

        String ans = prefix + mid  + suffix;

        return  ans;

    }

}