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

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;
    }
}