leetcode-shortest-palindrome

发表于   |   分类于 ，   |  

题目大意

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

　　在字符串之前加最少的字符使得新的字符串为回文串。

题目分析

　　本题要先求出最长回文前缀，利用了kmp算法中的辅助数组，关于kmp算法可以看我之前的博客，如果理解了lps数组的含义，那么就很好解本题了，原字符串s，原字符串的s的反转为s_rev，那么s+"#"+s_rev的lps数组的最后一项即是字符串s的最长的回文前缀得长度，再经过简单的处理就是答案了。

代码

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
36
37
38
39
public class Solution {
    public String shortestPalindrome(String s) {
        if (s.equals("")) {
            return "";
        }
        String sr = new StringBuilder(s).reverse().toString();
        StringBuilder sb = new StringBuilder();
        sb.append(s);
        sb.append("#");
        sb.append(sr);
        System.out.println(sb.toString());
        char[] c = sb.toString().toCharArray();
        int len = c.length;
        int[] lps = new int[len];
        // build lps array
        int preLen = 0;
        int i = 1;
        while (i < len) {
          if (c[preLen] == c[i]) {
            lps[i] = preLen + 1;
            i++;
            preLen++;
          } else {
            if (preLen == 0) {
              lps[i] = 0;
              i++;
            } else {
              preLen = lps[preLen - 1];
            }
          }
        }
        StringBuilder ans = new StringBuilder();
        for (int ii = s.length() - 1; ii >= lps[len - 1] ; ii--) {
            ans.append(c[ii]);
        }
        ans.append(s);
        return ans.toString();
    }
}

　　时间复杂度: O(n)