算法字符串

子序列匹配

字数统计: 2.8k字   |   阅读时长: 13分
, , , , ,

摘要: 子序列匹配问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 字符串精确匹配 中我们学习了字符串精确匹配的问题，本文我们看一下子序列匹配问题，涉及到贪心、动态规划、序列自动机等算法。题目和解法总览如下：

392. 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”ace”是”abcde”的一个子序列，而”aec”不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

示例 1：
输入：s = “abc”, t = “ahbgdc”
输出：true

示例 2：
输入：s = “axc”, t = “ahbgdc”
输出：false

提示：

1
2
3
0 <= s.length <= 100
0 <= t.length <= 10^4
两个字符串都只由小写字符组成。

算法1: 动态规划

LCS 的变种：

1
2
3
4
5
6
7
8
9
10
11
12
状态定义：
dp[i][j] := s[0..i-1] 是否是 t[0..j-1] 的子序列

初始化：
dp[0][0..m] = true
dp[1..n][0] = false

答案：
dp[n][m]

状态转移：
dp[i][j] = dp[i][j-1] || (dp[i - 1][j - 1] && s[i-1] == t[j-1])

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n = s.size(), m = t.size();
        vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
        for(int j = 0; j <= m; ++j)
            dp[0][j] = true;
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                dp[i][j] = dp[i][j - 1] || (dp[i - 1][j - 1] && s[i - 1] == t[j - 1]);
        return dp[n][m];
    }
};

算法2: 贪心 + 双指针

1
2
s = ch1, ch2, ..., chn
在 t 中依次找到最左边的 ch1, ch2, ..., chn，只要能在 s 耗尽前都找到，就可以匹配

维护贪心的算法：双指针(双串单向)。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int ns = s.size(), nt = t.size();
        if(ns == 0) return true;
        if(nt == 0) return false;
        if(ns > nt) return false;
        int is = 0;
        for(int it = 0; it < nt; ++it)
        {
            if(t[it] == s[is])
            {
                ++is;
                if(is == ns) return true;
            }
        }
        return false;
    }
};

算法3: 贪心 + 二分

在贪心算法中，将维护贪心策略的算法从双指针改为二分：

1
2
枚举 s 中字符，当前字符为 ch，上一个字符匹配到的位置的后一个位置记为 prev，初始 prev=0
在 t[prev..m-1] 找到最左边的 ch，在 ch 的下标数组中二分地找大于等于 prev 的第一个位置

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<int>> mappings(26);
        int m = t.size();
        for(int i = 0; i < m; ++i)
            mappings[t[i] - 'a'].push_back(i);
        int n = s.size();
        int prev = 0;
        for(int i = 0; i < n; ++i)
        {
            const vector<int> &idxs = mappings[s[i] - 'a'];
            auto it = lower_bound(idxs.begin(), idxs.end(), prev);
            if(it == idxs.end())
                return false;
            prev = *it + 1;
        }
        return true;
    }
};

算法4：序列自动机

序列自动机的算法和代码参考文章 序列自动机。

792. 匹配子序列的单词数

给定字符串 s 和字符串数组 words, 返回 words[i] 中是s的子序列的单词个数 。

字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。

例如， “ace” 是 “abcde” 的子序列。

注意:

1
2
3
4
所有在words和 S 里的单词都只由小写字母组成。
S 的长度在 [1, 50000]。 (N)
words 的长度在 [1, 5000]。 (L)
words[i]的长度在[1, 50]。 (W)

示例 1:
输入: s = “abcde”, words = [“a”,”bb”,”acd”,”ace”]
输出: 3
解释: 有三个是 s 的子序列的单词: “a”, “acd”, “ace”。

示例 2:
输入: s = “dsahjpjauf”, words = [“ahjpjau”,”ja”,”ahbwzgqnuk”,”tnmlanowax”]
输出: 2

算法1：贪心 + 二分

1
2
3
预处理 S 中各个字符的下标数组
枚举 w = words[i]:
    判断 w 是否是 S 的子序列

时间复杂度 $O(N + LW\log N)$

代码 (C++)

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
class Solution {
public:
    int numMatchingSubseq(string S, vector<string>& words) {
        int n = S.size();
        vector<vector<int>> mappings(26);
        for(int i = 0; i < n; ++i)
            mappings[S[i] - 'a'].push_back(i);
        int ans = 0;
        for(const string &word: words)
        {
            int w = word.size();
            int prev = 0;
            bool flag = true;
            for(int i = 0; i < w; ++i)
            {
                const vector<int> &idxs = mappings[word[i] - 'a'];
                auto it =lower_bound(idxs.begin(), idxs.end(), prev);
                if(it == idxs.end())
                {
                    flag = false;
                    continue;
                }
                prev = *it + 1;
            }
            if(flag)
                ++ans;
        }
        return ans;
    }
};

算法2：序列自动机

先对 t 建立序列自动机，然后依次查询 s1, s2, …, sk 即可。

代码 (C++)

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
53
54
55
56
57
58
class SeqAM
{
public:
    SeqAM(){}
    SeqAM(const string& t)
    {
        build(t);
    }

    void build(const string& t)
    {
        // 由字符串 t 建立序列自动机
        int n = t.size();
        int m = 26; // 字母表中的字符数
        nxt = vector<vector<int>>(n + 1, vector<int>(m, -1));
        
        for(int i = t.size() - 1; i >= 0; --i)
        {
            for(int j = 0; j < 26; ++j)
                nxt[i][j] = nxt[i + 1][j];
            nxt[i][t[i] - 'a'] = i; // 在 nxt[i] 这一行只更新了第 t[i] - 'a' 这一列。
        }
    }

    bool find(const string& s)
    {
        int l = s.size();
        int p = -1;
        for(int i = 0; i < l; ++i)
        {
            p = nxt[p + 1][s[i] - 'a'];
            if(p == -1)
                return false;
        }
        return true;
    }

private:
    vector<vector<int>> nxt;
};

class Solution {
public:
    int numMatchingSubseq(string S, vector<string>& words) {
        int n = S.size();
        SeqAM seq_am(S);
        int ans = 0;
        for(const string &word: words)
        {
            int w = word.size(fw);
            if(w > n)
                continue;
            if(seq_am.find(word))
                ++ans;
        }
        return ans;
    }
};

44. 通配符匹配

给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 ‘?’ 和 ‘*’ 匹配规则的通配符匹配：

  • ‘?’ 可以匹配任何单个字符。
  • ‘*’ 可以匹配任意字符序列（包括空字符序列）。

判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

提示：

1
2
3
0 <= s.length, p.length <= 2000
s 仅由小写英文字母组成
p 仅由小写英文字母、'?' 或 '*' 组成

示例 1：
输入：s = “aa”, p = “a”
输出：false
解释：”a” 无法匹配 “aa” 整个字符串。

示例 2：
输入：s = “aa”, p = ““
输出：true
解释：’‘ 可以匹配任意字符串。

示例 3：
输入：s = “cb”, p = “?a”
输出：false
解释：’?’ 可以匹配 ‘c’, 但第二个 ‘a’ 无法匹配 ‘b’。

算法1：动态规划

LCS 的变种：

1
2
3
4
5
6
7
8
9
10
11
12
13
状态定义：
dp[i][j] := s[0..i-1] 与 t[0..j-1] 是否匹配

初始化：
dp[0][0] = true
dp[0][j] = true   (1 <= j <= m && p[j - 1] == '*')

答案：
dp[n][m]

状态转移：
dp[i][j] = dp[i - 1][j - 1]  (s[i - 1] == p[j - 1] || p[j - 1] == '?')
         = dp[i][j - 1]      (p[j - 1] == '*')

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();

        vector<vector<bool> > dp(n + 1, vector<bool>(m + 1, false));
        dp[0][0] = true;
        // j = 0 的列, 空模式匹配 s, 无需初始化
        // 初始化 i = 0 的行, p 匹配空串
        int j = 1;
        while(j <= m && p[j - 1] == '*')
            dp[0][j++] = true;

        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
            {
                if(s[i - 1] == p[j - 1] || p[j - 1] == '?')
                    dp[i][j] = dp[i - 1][j - 1];
                else if(p[j - 1] == '*')
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
            }
        return dp[n][m];
    }
};

算法2: 贪心

有点类似 kmp 的思想，与子序列匹配的贪心很像：

1
2
p=str1*str2*...*strm
在s中依次找到最左边的str1,str2,...,strm，只要能在s耗尽前都找到，就可以匹配

维护贪心的算法依然是双串单向双指针。

另：在 s 中精确匹配 str1, str2, …, strm 这步操作可以用 AC 自动机优化。

代码 (C++)

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
class Solution {
public:
    bool isMatch(string s, string p) {
        if(s.empty() && p.empty()) return true;
        if(s.empty() || p.empty()) return false;
        int n = s.size(), m = p.size();
        int i = 0, j = 0;
        int istar = -1, jstar = -1;
        while(i < n)
        {
            if(j < m && (s[i] == p[j] || p[j] == '?'))
            {
                ++i;
                ++j;
            }
            else if(j < m && p[j] == '*')
            {
                istar = i;
                jstar = j;
                ++j;
            }
            else if(istar >= 0)
            {
                ++istar;
                i = istar;
                j = jstar + 1;
            }
            else
                return false;
        }
        while(j < m)
            if(p[j++] != '*')
                return false;
        return true;
    }
};

1055. 形成字符串的最短路径

对于任何字符串，我们可以通过删除其中一些字符（也可能不删除）来构造该字符串的 子序列 。(例如，“ace” 是 “abcde” 的子序列，而 “aec” 不是)。

给定源字符串 source 和目标字符串 target，返回 源字符串 source 中能通过串联形成目标字符串 target 的 子序列 的最小数量 。如果无法通过串联源字符串中的子序列来构造目标字符串，则返回 -1。

提示：

1
2
1 <= source.length, target.length <= 1000
source 和 target 仅包含英文小写字母。

示例 1：
输入：source = “abc”, target = “abcbc”
输出：2
解释：目标字符串 “abcbc” 可以由 “abc” 和 “bc” 形成，它们都是源字符串 “abc” 的子序列。

示例 2：
输入：source = “abc”, target = “acdbc”
输出：-1
解释：由于目标字符串中包含字符 “d”，所以无法由源字符串的子序列构建目标字符串。

示例 3：
输入：source = “xyz”, target = “xzyxz”
输出：3
解释：目标字符串可以按如下方式构建： “xz” + “y” + “xz”。

算法: 动态规划 + 贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
pos[i] := 当 t[0..i] 取到所需最少个数的 s 后，t[i] 在 s 中的位置 (贪心)

状态定义
dp[i] := t[0..i] 所需的最少个数 (t 中的字符 s 中都有)

初始化
dp[0] = 1

答案
dp[m-1]

状态转移
dp[i] = dp[i - 1] + 1 (s[pos[i - 1] .. n - 1] 中无 t[i])
        dp[i]         (s[pos[i - 1] .. n - 1] 中有 t[i])

代码 (C++)

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
class Solution {
public:
    int shortestWay(string source, string target) {
        string &s = source, &t = target;
        int n = s.size(), m = t.size();
        vector<set<int>> idxs(26); // 字符 -> 若干索引
        for(int i = 0; i < n; ++i)
            idxs[s[i] - 'a'].insert(i);
        for(const char& ch: target)
            if(idxs[ch - 'a'].empty())
                return -1;
        // t 中的字符均在 s 中出现
        vector<int> dp(m, -1); // dp[i] := t[0..i] 所需的 s 个数, dp[0] = 1;
        vector<int> pos(m, -1); // pos[i] := 最优情况下 t[i] 在 s 的位置(下标)
        dp[0] = 1;
        pos[0] = *idxs[t[0] - 'a'].begin();
        for(int i = 1; i < m; ++i)
        {
            // 在 (pos[i - 1]..n-1] 中找 t[i]
            auto it = idxs[t[i] - 'a'].upper_bound(pos[i - 1]);
            if(it == idxs[t[i] - 'a'].end())
            {
                dp[i] = dp[i - 1] + 1;
                pos[i] = *idxs[t[i] - 'a'].begin();
            }
            else
            {
                dp[i] = dp[i - 1];
                pos[i] = *it;
            }
        }
        return dp[m - 1];
    }
};
Share