> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/string/kmp/214-shortest-palindrome.md).

# 214 Shortest Palindrome

## 214. [Shortest Palindrome](https://leetcode.com/problems/shortest-palindrome/description/)

## 1. Question

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.

For example:

Given`"aacecaaa"`, return`"aaacecaaa"`.

Given`"abcd"`, return`"dcbabcd"`.

## 2. Implementation

**(1) Brute Force**

```java
class Solution {
    public String shortestPalindrome(String s) {
        String revStr = new StringBuilder(s).reverse().toString();
        int n = s.length();

        for (int i = 0; i < n; i++) {
            if (s.substring(0, n - i).equals(revStr.substring(i))) {
                return revStr.substring(0, i) + s;
            }
        }
        return "";
    }
}
```

**(2) KMP Algorithm**

思路: 这题的本质是找出从第一位开始算起的最长palindrome substring,我们设为k，输入string的长度为n，然后需要插入的字符数的个数就等于n - k，这样是最短的。而找出从第一位开始算的最长palindrome substring的思路恰好也是我们计算KMP lookup table的本质(找出最长的共同前缀和后缀的长度)一样。关于KMP中求next数组的思想可以参考这篇[文章](https://www.cnblogs.com/c-cloud/p/3224788.html)。这里需要注意的一个地方是我们必须在s 和 revStr中间插入一个特殊符号，否则最后的的结果是不正确的。比如,s = "aaaa", s + revStr = “aaaaaaaa” , 那么最长的共同前缀后缀是7，这显然不对，因为超过s的长度。

```java
class Solution {
    public String shortestPalindrome(String s) {
        String revStr = new StringBuilder(s).reverse().toString();
        int[] next = getNextTable(s + "#" + revStr);

        return revStr.substring(0, s.length() - next[next.length - 1]) + s;
    }

    public int[] getNextTable(String s) {
        int[] next = new int[s.length()];
        int len = 0;
        for (int i = 1; i < s.length(); i++) {
            while (len > 0 && s.charAt(i) != s.charAt(len)) {
                len = next[len - 1];
            }

            if (s.charAt(i) == s.charAt(len)) {
                ++len;
            }
            next[i] = len;
        }
        return next;
    }
}
```

## 3. Time & Space Complexity

**Brute Force:** 时间复杂度O(n^2), 空间复杂度O(n)

**KMP Algorithm:** 时间复杂度O(n), 空间复杂度O(n)