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

# 214.Shortest-Palindrome

## 214. Shortest Palindrome

## 题目地址

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

## 题目描述

```
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.

Example 1:

Input: "aacecaaa"
Output: "aaacecaaa"
Example 2:

Input: "abcd"
Output: "dcbabcd"
```

## 代码

### Approach # Brute Force

Time complexity: O(n^2)

```java
class Solution {
  public String shortestPalindrome(String s) {
    int n = s.length();
    String reversed = new StringBuilder(s).reverse().toString();
    int j = 0;
    for (int i = 0; i < n; i++) {
      if (s.substring(0, n-i) == reversed.substring(i)) {
        return resersed.substring(0, i) + s;
      }
    }

    return "";
  }
}
```

### Approach #1 Two pointers and recursion

```java
class Solution {
  public String shortestPalindrome(String s) {
        int n = s.length();
    int i = 0;
    for (int j = n - 1; j >= 0; j--) {
      if (s[i] == s[j]) {
        i++;
      }
    }
    if (i == n)     return s;

    String remain = s.substring(i);
    String prefix = new StringBuilder(remain).reverse().toString();
    String subfix = shortestPalindrome(s.substring(0, i)) + remain;
    return prefix + subfix;
  }
}
```

### Approach #3 KMP

<https://leetcode.com/problems/shortest-palindrome/discuss/60113/Clean-KMP-solution-with-super-detailed-explanation>

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

    return new StringBuilder(s.substring(table[table.length - 1])).reverse().toString() + s;
  }

  public int[] getTable(String s) {
    int[] table = new int[s.length()];

    int index = 0;
    for (int i = 1; i < s.length(); ) {
        if (s.charAt(index) == s.charAt(i)) {
            table[i] = ++index;
            i++;
        } else {
            if (index > 0) {
                index = table[index-1];
            } else {
                index = 0;
                i ++;
            }
        }
    }
    return table;
  }
}
```