Noob
0%

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.

For example:

Given “aacecaaa”, return “aaacecaaa”.

Given “abcd”, return “dcbabcd”.

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

中心点扩散法

只能在字符串头部插入字符，因此需要首先找出包含头部字符的最长回文子串，然后将剩下的字符翻转后插入头部即可，采用中心点扩散法求包含头部的最长回文子串代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public String shortestPalindrome(String s) {
    int maxLen = 0;
    for(int i = 0; i < s.length(); ++i) {
        int len = scanMaxLen(s, i, i);
        if(maxLen < len)
            maxLen = len;
        len = scanMaxLen(s, i, i + 1);
        if(maxLen < len)
            maxLen = len;
    }
    StringBuilder add = new StringBuilder(s.substring(maxLen, s.length()));
    add.reverse();
    return add.append(s).toString();
}

private int scanMaxLen(String s, int l, int r){
    int i = l, j = r;
    while(i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
        --i;
        ++j;
    }
    if(i >= 0) return 0;
    return l == r ? (l - i) + (j - r) - 1 : (l - i) + (j - r);
}

Manacher算法

采用Manacher算法求包含头部的最长回文子串代码如下，注意p[i] - 1的值是以i为中心的最长回文子串的长度，i == p[i]时即表示以i为中心的回文子串包含首字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public String shortestPalindrome(String s) {
    if(s == null || s.length() <= 1) return s;
    String ps = process(s);
    int[] p = new int[ps.length()];
    int mx = 0, id = 1;
    for(int i = 1; i < ps.length() - 1; ++i) {
        p[i] = mx > i ? Math.min(p[2 * id - i], mx - i) : 1;
        while(ps.charAt(i - p[i]) == ps.charAt(i + p[i]))
            ++p[i];
        if(mx < i + p[i]) {
            mx = i + p[i];
            id = i;
        }
    }
    int maxLen = 0;
    for(int i = 1; i < ps.length(); ++i) {
        if(maxLen < p[i] && i == p[i]) {
            maxLen = p[i];
        }
    }
    StringBuilder sb = new StringBuilder(s.substring(maxLen - 1));
    return sb.reverse().append(s).toString();
}

private String process(String s) {
    StringBuilder sb = new StringBuilder();
    sb.append('$');
    for(char ch : s.toCharArray()) {
        sb.append('#');
        sb.append(ch);
    }
    sb.append('#');
    sb.append('^');
    return sb.toString();
}