214. Shortest Palindrome

Link

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"

Solution

 // for aaaaabcaaaaaa O(n^2)
    public String shortestPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        int index = s.length() - 1;

        //目的在找到 index ,能使s.substring(0, index+1)是回文
        // s.substring(index+1).reverse + s 會是Palindrome

        while (i < j) {
            if (s.charAt(i) == s.charAt(j)) {
                i++;
                j--;
            } else {
                i = 0; //回到頭開始找是否有辦法先構成部分回文
                index--; //表示目前index不可能構成局部回文
                j = index;
            }
        }
        return new StringBuilder(s.substring(index + 1)).reverse().toString() + s;
    }