package leetcode;

/**
 * https://leetcode.com/problems/shortest-palindrome/
 */
public class Problem214 {
    public String shortestPalindrome(String s) {
        int i = 0;
        int j = s.length() - 1;
        int k = j;
        String prefix = "";
        outer: while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                for (int x = k; x >= j; x--) {
                    prefix += s.charAt(x);
                    if (isPalindrome(prefix + s)) {
                        break outer;
                    }
                }
                i = 0;
                j--;
                k = j;
            } else {
                i++;
                j--;
            }
        }
        return prefix + s;
    }

    private static boolean isPalindrome(String s) {
        for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Problem214 prob = new Problem214();
        System.out.println(prob.shortestPalindrome("aacecaaa")); // "aaacecaaa"
        System.out.println(prob.shortestPalindrome("abcd")); // "dcbabcd"
        System.out.println(prob.shortestPalindrome("aabaa")); // "aabaa"
        System.out.println(prob.shortestPalindrome("aaaa")); // "aaaa"
        System.out.println(prob.shortestPalindrome("aaba")); // "abaaba"
        System.out.println(prob.shortestPalindrome("aababa")); // "ababaababa"
    }
}
@@ -161,249 +161,91 @@
     
-int i = 0;%0A        int j = s.length() - 1;%0A        int k = j;%0A        String prefix = %22%22;%0A        outer: while (i %3C j) %7B%0A            if (s.charAt(i) != s.charAt(j)) %7B%0A                for (int x = k; x %3E= j; x--) %7B%0A                   
+String reversed = new StringBuilder(s).reverse().toString();%0A        String
  prefix 
 += s
@@ -244,497 +244,136 @@
 fix 
-+
 = 
-s.charAt(x);%0A                    if (isPalindrome(prefix + s)) %7B%0A                        break outer;%0A                    %7D%0A                %7D%0A                i = 0;%0A                j--;%0A                k = j;%0A            %7D else %7B%0A                i++;%0A                j--;%0A            %7D%0A        %7D%0A        return prefix + s;%0A    %7D%0A%0A    private static boolean isPalindrome(String s) %7B%0A        for (int i = 0, j = s.length() - 1; i %3C j; i++, j--) %7B%0A            if (s.charAt(i) != s.charAt(j
+%22%22;%0A        for (int i = 0; i %3C s.length(); i++) %7B%0A            if (s.substring(0, s.length() - i).equals(reversed.substring(i)
 )) %7B
@@ -393,20 +393,13 @@
     
+b
 re
-turn false
+ak
 ;%0A  
@@ -422,576 +422,78 @@
     
-%7D%0A        return true;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem214 prob = new Problem214();%0A        System.out.println(prob.shortestPalindrome(%22aacecaaa%22)); // %22aaacecaaa%22%0A        System.out.println(prob.shortestPalindrome(%22abcd%22)); // %22dcbabcd%22%0A        System.out.println(prob.shortestPalindrome(%22aabaa%22)); // %22aabaa%22%0A        System.out.println(prob.shortestPalindrome(%22aaaa%22)); // %22aaaa%22%0A        System.out.println(prob.shortestPalindrome(%22aaba%22)); // %22abaaba%22%0A        System.out.println(prob.shortestPalindrome(%22aababa%22)); // %22ababaababa%22
+    prefix += reversed.charAt(i);%0A        %7D%0A        return prefix + s;
 %0A   

Solve problem 214