题目描述
如果我们可以将小写字母插入模式串 pattern
得到待查询项 query
,那么待查询项与给定模式串匹配。(我们可以在任何位置插入每个字符,也可以插入 0 个字符。)
给定待查询列表 queries
,和模式串 pattern
,返回由布尔值组成的答案列表 answer
。只有在待查项 queries[i]
与模式串 pattern
匹配时,answer[i]
才为 true
,否则为 false
。
样例
输入:
queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"],
pattern = "FB"
输出:[true,false,true,true,false]
示例:
"FooBar" 可以这样生成:"F" + "oo" + "B" + "ar"。
"FootBall" 可以这样生成:"F" + "oot" + "B" + "all"。
"FrameBuffer" 可以这样生成:"F" + "rame" + "B" + "uffer"。
输入:
queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"],
pattern = "FoBa"
输出:[true,false,true,false,false]
解释:
"FooBar" 可以这样生成:"Fo" + "o" + "Ba" + "r"。
输出:
queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"],
pattern = "FoBaT"
输入:[false,true,false,false,false]
解释:
"FooBarTest" 可以这样生成:"Fo" + "o" + "Ba" + "r" + "T" + "est"。
说明
1 <= queries.length <= 100
1 <= queries[i].length <= 100
1 <= pattern.length <= 100
- 所有字符串都仅由大写和小写英文字母组成。
算法1
(动态规划) $O(qmn)$
- 对于每个询问,采用动态规划做匹配。
- 设 $f(i, j)$ 表示
pattern
的前i
个字符是否匹配待查询字符串的前j
个字符,字符串的下标都从 1 开始。 - 初始时 $f(0, 0) = true$。其余为 $false$。
- 转移时,如果 $pattern[i] == q[j]$,则转移 $f(i, j) = f(i, j) \text{ or } f(i - 1, j - 1)$。如果 $q[j]$ 为小写字母,则也可以转移 $f(i, j) = f(i, j) \text{ or } f(i, j - 1)$。
- 最终答案为 $f(m, n)$。
时间复杂度
- 假设查询数为 $q$,模式串的长度为 $m$,每个待查询字符串的长度为 $n$。
- 对于每个查询,状态数为 $O(mn)$,转移时间为常数,故总时间复杂度为 $O(qmn)$。
空间复杂度
- 需要额外 $O(q)$ 的空间存储答案,以及 $O(mn)$ 的空间存储动态规划的状态。
- 故总空间复杂度为 $O(q + mn)$。
C++ 代码
class Solution {
public:
vector<bool> camelMatch(vector<string>& queries, string pattern) {
vector<bool> ans;
int m = pattern.size();
for (const auto &q : queries) {
int n = q.size();
vector<vector<bool>> f(m + 1, vector<bool>(n + 1, false));
f[0][0] = true;
for (int i = 0; i <= m; i++)
for (int j = 1; j <= n; j++) {
if (i > 0 && j > 0 && pattern[i - 1] == q[j - 1])
f[i][j] = f[i][j] || f[i - 1][j - 1];
if (j > 0 && q[j - 1] >= 'a' && q[j - 1] <= 'z')
f[i][j] = f[i][j] || f[i][j - 1];
}
ans.push_back(f[m][n]);
}
return ans;
}
};
算法2
(贪心匹配) $O(q(n + m))$
- 我们只需要尽可能的让
pattern
与待查询字符串进行匹配。 - 如果
j < m
且q[i] == pattern[j]
,则直接匹配这一位。否则,如果q[i]
是大写字母,则直接宣布失败。
时间复杂度
- 假设查询数为 $q$,模式串的长度为 $m$,每个待查询字符串的长度为 $n$。
- 对于每个查询,仅需要 $O(n + m)$ 的时间,故总时间复杂度为 $O(q(n + m))$。
空间复杂度
- 需要额外 $O(q)$ 的空间存储答案。
C++ 代码
class Solution {
public:
vector<bool> camelMatch(vector<string>& queries, string pattern) {
vector<bool> ans;
int m = pattern.size();
for (const auto &q : queries) {
int n = q.size();
int j = 0;
for (int i = 0; i < n; i++) {
if (j < m && q[i] == pattern[j])
j++;
else if (q[i] >= 'A' && q[i] <= 'Z') {
j = -1;
break;
}
}
ans.push_back(j == m);
}
return ans;
}
};