子序列匹配

  |  

摘要: 子序列匹配问题

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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