LeetCode总结——字符串相关算法

发表于 | 分类于 | 阅读次数:
字数统计: 1,286 字

总结在LeetCode中字符串相关的常用的一些算法

KMP 算法

KMP算法解决的是两个字符串的匹配问题（一个字符串是不是另外一个字符串的子串）

暴力法所需要的时间复杂度是O(n*m)，KMP算法能够优化到O(n)。KMP算法的核心是使用一个next数组实现匹配的加速

next数组

最长前缀后缀：一个字符串中所有的前缀和其所有的后缀中最长的相等的长度，比如说“abcabc”的最长前缀后缀为”abc”

给定一个串s的next数组next[]，其每一位next[i]表示串s[0…i-1]中最长前缀后缀

使用next数据对字符串匹配进行加速：s1中查找是否有子串s2，如果s1[i]匹配到s2[j]的时候不相等，并且此时next[j]=k，此时不需要重新回到s1[1]继续进行匹配，而是用s2[k]继续和s1[i]进行匹配，依次类推

因为next数组是找到了最长前缀后缀的，所以其能够从最长前缀的匹配跳到最长后缀的匹配，因为中间不可能出现匹配的情况，如果出现匹配那么表示当前next计算的不可能是”最长“前缀后缀。

next数组求法

规定next[0] = -1， 因为其前面没有字符串；next[1] = 0，因为其前面的字符串中只有一个字符，后面的next值的计算取决于前面的next值：

判断当前位置的字符和最长前缀的后一个字符是否相等，如果相等则next[i] = next[i-1] + 1，如果不等再判断最长前缀的最长前缀和其相等不相等，如果还不相等就继续找最长前缀，直到最长前缀长度为0的时候表示没有找到，这个时候next[i] = 0

LeetCode 028

Implement strStr()

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
class Solution {
public:
    int strStr(string s, string p) {
        int len = p.size();
        if(len == 0) return 0;
        // 生成next数组
        vector<int> next(len, 0);
        getNext(next, p);
        // 两个数组的遍历指针
        int i = 0, j = 0;
        while(i < s.size() && j < len)
        {
            if(s[i] == p[j])
            {
                i++;
                j++;
            }
            else
            {
                if(j == 0) i++;
                // 根据next数组中的信息进行重新指向
                else j = next[j];
            }
        }
        return j == len ? i - j : -1;
    }
    
    void getNext(vector<int> &next, string p)
    {
        next[0] = -1;
        // k表示最长前缀后缀的长度
        int k = -1, i = 0;
        // 计算到最后一位
        while(i < p.size() - 1)
        {
            // 相匹配的时候对next数组赋值
            if(k == -1 || p[i] == p[k])
                next[++i] = ++k;
            else
                k = next[k];
        }
    }
};

Manacher 算法

Manacher 算法解决的是字符串中最长的回文子串的问题

暴力法（技巧：中间添加辅助字符）解决这个问题的时间复杂度为O(n^2)，Manacher算法能够时间复杂度优化为O(n)

几个概念

  • 回文半径数组，以i为中心的的回文的半径长度
  • 回文右边界，遍历过的回文能够达到的最右的下标
  • 右边界中心位置，回文右边界对应的回文中心点下标

算法过程

和暴力解法一样从左向右扩充判断，有以下几种情况：

  1. 当前位置不在回文右边界里面，暴力扩充
  2. 当前位置在回文右边界里面，其关于右边界中心的对称点的回文区域在左边界里面，其回文半径和其对称点一样
  3. 当前位置在回文右边界里面，其关于右边界中心的对称点的回文左区域超过回文左边界，其回文半径为r-i
  4. 当前位置在回文右边界里面，其关于右边界中心的对称点的回文左区域与回文左边界重合（压线），其回文半径需要在r-i的基础上往后判断

LeetCode 005

Longest Palindromic Substring

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
51
52
class Solution {
public:
    // Manacher 算法
    string longestPalindrome(string s) {
        // 添加辅助字符#
        string new_s;
        new_s.push_back('#');
        for(int i = 0; i < s.size(); i++)
        {
            new_s.push_back(s[i]);
            new_s.push_back('#');
        }
        s = new_s;
        int len = s.size();
        if(len == 0) return 0;
        // 回文半径数组
        vector<int> pArr(len, 0);
        // C表示回文中心， R表示回文右边界
        int C = -1, R = -1;
        int maxv = INT_MIN, maxi = 0;
        for(int i = 0; i < len; i++)
        {
            // 在回文右边界里面与否的区分
            // 此时pArr表示的是起码不用验的区域 
            pArr[i] = R > i ? min(pArr[2*C - i], R - i) : 1;
            // 区域没有越界
            while(i + pArr[i] < len && i - pArr[i] > -1)
            {
                // 情况1+4 扩充
                if(s[i + pArr[i]] == s[i - pArr[i]])
                    pArr[i]++;
                // 情况2+3
                else
                    break;
            }
            if(i + pArr[i] > R)
            {
                R = i + pArr[i];
                C = i;
            }
            if(maxv < pArr[i])
            {
                maxv = pArr[i];
                maxi = i;
            }
        }
        string res;
        for(int i = maxi - maxv + 1; i <= maxi + maxv - 1; i++)
            if(s[i] != '#') res.push_back(s[i]);
        return res;
    }
};