1
class Solution {
2
  public String shortestPalindrome(String s) {
3
    for (int i = s.length() - 1; i >= 0; i--) {
4
      if (isPalindrome(s, 0, i)) {
5
        String toAppend = s.substring(i + 1);
6
        String result = new StringBuilder(toAppend).reverse().append(s).toString();
7
        return result;
8
      }
9
    }
10
    String result = new StringBuilder(s).reverse().append(s).toString();
11
    return result;
12
  }
13

14
  boolean isPalindrome(String s, int left, int right) {
15
    while (left < right) {
16
      if (s.charAt(left) != s.charAt(right)) return false;
17
      left++;
18
      right--;
19
    }
20
    return true;
21
  }
22
}