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:

    1. Input: "aacecaaa"
    2. Output: "aaacecaaa"

    Example 2:

    1. Input: "abcd"
    2. Output: "dcbabcd"

    题意

    给定一个字符串s，要求在它前面添加字符，使得到的新字符串为回文串，且长度最短。

    思路

    在原字符串s中找到以左端点为开头的最长回文子串，将s中剩余的右半部分逆置后放在原字符串之前，得到的一定是最短的回文串，如图：
    image.png

    所以问题就转化为了找到原字符串中左侧的最长回文子串。

    常规方法用214. Shortest Palindrome (H) 待完善KMP - 图2的时间即可找到回文子串。另有两种214. Shortest Palindrome (H) 待完善KMP - 图3复杂度的方法：

    Manacher马拉车算法：具体解析详见博客园 - BIT祝威

    KMP：待完善

    代码实现 - Two Pointers

    1. class Solution {
    2.     public String shortestPalindrome(String s) {
    3.         int maxLength = 1;
    5.         for (int i = s.length(); i >= 1; i--) {
    6.             if (isPalindrome(s.substring(0, i))) {
    7.                 maxLength = i;
    8.                 break;
    9.             }
    10.         }
    12.         StringBuilder sb = new StringBuilder();
    13.         for (int i = s.length() - 1; i >= maxLength; i--) {
    14.             sb.append(s.charAt(i));
    15.         }
    16.         sb.append(s);
    18.         return sb.toString();
    19.     }
    21.     private boolean isPalindrome(String s) {
    22.         int left = 0, right = s.length() - 1;
    23.         while (left < right) {
    24.             if (s.charAt(left++) != s.charAt(right--)) {
    25.                 return false;
    26.             }
    27.         }
    28.         return true;
    29.     }
    30. }

    代码实现 - Manacher马拉车算法

    1. class Solution {
    2.     public String shortestPalindrome(String s) {
    3.         int maxLen = findMaxPalinLength(s);
    4.         StringBuilder sb = new StringBuilder();
    5.         for (int i = s.length() - 1; i >= maxLen; i--) {
    6.             sb.append(s.charAt(i));
    7.         }
    8.         sb.append(s);
    9.         return sb.toString();
    10.     }
    12.     private int findMaxPalinLength(String s) {
    13.         String t = transform(s);
    14.         int[] p = new int[t.length()];
    15.         int C = 0;                // 中心位置
    16.         int R = 0;                // 右边界
    17.         int maxLen = 0;            // 回文串最大半径
    19.         for (int i = 0; i < t.length(); i++) {
    20.             int j = 2 * C - i;            // j是i关于C的对称点
    22.             p[i] = R >= i ? Math.min(p[j], R - i) : 0;        // 分三种情况进行赋值
    24.             // 回文半径可能增加的情况
    25.             while (i + p[i] + 1 < t.length() && i - p[i] - 1 >= 0 && t.charAt(i + p[i] + 1) == t.charAt(i - p[i] - 1)) {
    26.                 p[i]++;
    27.             }
    29.             // 找到以左端点为起点的最长回文字串
    30.             if (i - p[i] == 0 && p[i] > maxLen) {
    31.                 maxLen = p[i];
    32.             }
    34.             // 更新中心点和右边界
    35.             if (i + p[i] > R) {
    36.                 C = i;
    37.                 R = i + p[i];
    38.             }
    39.         }
    41.         return maxLen;
    42.     }
    44.     // 字符串转换
    45.     private String transform(String s) {
    46.         StringBuilder sb = new StringBuilder();
    47.         for (int i = 0; i < s.length(); i++) {
    48.             sb.append('#').append(s.charAt(i));
    49.         }
    50.         sb.append('#');
    51.         return sb.toString();
    52.     }
    53. }

    代码实现 - KMP