# 0214. Shortest Palindrome

<https://leetcode.com/problems/shortest-palindrome>

## Description

You are given a string `s`. You can convert `s` to a palindrome by adding characters in front of it.

Return *the shortest palindrome you can find by performing this transformation*.

**Example 1:**

```
**Input:** s = "aacecaaa"
**Output:** "aaacecaaa"
```

**Example 2:**

```
**Input:** s = "abcd"
**Output:** "dcbabcd"
```

**Constraints:**

* `0 <= s.length <= 5 * 104`
* `s` consists of lowercase English letters only.

## ac1: brute force

```java
class Solution {
    public String shortestPalindrome(String s) {
        // edge cases
        if (s == null || s.length() == 0 || isPalindrome(s, 0, s.length()-1)) return s;

        // walk backward
        int n = s.length();
        int i = n - 2;
        for (; i >= 0; i--) {
            if (isPalindrome(s, 0, i)) break;
        }

        // reversed tail
        StringBuilder sb = new StringBuilder();
        for (int j = n - 1; j > i; j--) {
            sb.append(s.charAt(j));
        }

        // append to head
        sb.append(s);

        return sb.toString();
    }

    private boolean isPalindrome(String s, int l, int r) {
        if (l > r) return false;
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }
}
```