Keshawn_lu's Blog

Leetcode 214. 最短回文串

字符串 KMP
字数统计: 525阅读时长: 2 min
2020/08/29 Share

题目简介：

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

示例 1:

1
2
输入: "aacecaaa"
输出: "aaacecaaa"

示例 2:

1
2
输入: "abcd"
输出: "dcbabcd"

思路：

第一次尝试用KMP方法做题，有点头疼。

我们记s的逆转字符串为reverse_str，其实题目可以转换为s前缀和reverse_str后缀的最长公共部分，如下图所示：

这时我们可以将模式串定义为s + # + reverse_str(#用来分割)，将这个字符串的最长公共前后缀找到即可。

寻找最长公共前后缀的方法就要用到KMP了，我们需要求出next数组，具体方法如下：

  1. 定义一个k来表示之前的最长公共前后缀
  2. 若pattern[i - 1] == pattern[k]，则说明该字符也匹配到了，最长公共前后缀+1，next[i] = k + 1。
  3. 若pattern[i - 1] != pattern[k] && k == 0，则说明没有匹配的前后缀，next[i] = 0。
  4. 若pattern[i - 1] != pattern[k] && k != 0，则我们需要找字符串pattern[0 ... k]中的公共前后缀的长度，即k = next[k]。

找出模式串的最长公共前后缀后，返回reverse_str.substr(0, reverse_str.size() - max_common) + 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
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:

    int kmp_next(string& pattern){

        vector<int> next(pattern.size() + 1, 0);

        int k = 0;  //记录之前的最长公共前后缀

        next[0] = -1;
        next[1] = 0;    //一个字母没有前后缀

        int i = 2;
        while(i < next.size()){  //pattern索引比next数组索引小1

            if(pattern[i - 1] == pattern[k]){

                next[i] = k + 1;    //之前的前后缀长度+1
                k = next[i];    
                i++;
            }
            else if(k == 0){

                next[i] = 0;
                i++;
            }
            else{

                k = next[k];
            }
        }

        return next[next.size() - 1];   //返回该字符串的最长公共前后缀
    }


    string shortestPalindrome(string s) {

        string reverse_str = s;

        reverse(reverse_str.begin(), reverse_str.end());    //逆转字符串

        string pattern = s + '#' + reverse_str;

        int max_common = kmp_next(pattern);

        return reverse_str.substr(0, reverse_str.size() - max_common) + s;

    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网