第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
1023. 驼峰式匹配

题目地址(1023. 驼峰式匹配)

题目描述

1
如果我们可以将小写字母插入模式串 pattern 得到待查询项 query,那么待查询项与给定模式串匹配。(我们可以在任何位置插入每个字符,也可以插入 0 个字符。)
2
3
给定待查询列表 queries,和模式串 pattern,返回由布尔值组成的答案列表 answer。只有在待查项 queries[i] 与模式串 pattern 匹配时, answer[i] 才为 true,否则为 false。
4
5
6
7
示例 1:
8
9
输入:queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
10
输出:[true,false,true,true,false]
11
示例:
12
"FooBar" 可以这样生成:"F" + "oo" + "B" + "ar"。
13
"FootBall" 可以这样生成:"F" + "oot" + "B" + "all".
14
"FrameBuffer" 可以这样生成:"F" + "rame" + "B" + "uffer".
15
示例 2:
16
17
输入:queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBa"
18
输出:[true,false,true,false,false]
19
解释:
20
"FooBar" 可以这样生成:"Fo" + "o" + "Ba" + "r".
21
"FootBall" 可以这样生成:"Fo" + "ot" + "Ba" + "ll".
22
示例 3:
23
24
输出:queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBaT"
25
输入:[false,true,false,false,false]
26
解释:
27
"FooBarTest" 可以这样生成:"Fo" + "o" + "Ba" + "r" + "T" + "est".
28
29
30
提示:
31
32
1 <= queries.length <= 100
33
1 <= queries[i].length <= 100
34
1 <= pattern.length <= 100
35
所有字符串都仅由大写和小写英文字母组成。
Copied!

前置知识

  • 双指针

公司

  • 暂无

思路

这道题是一道典型的双指针题目。不过这里的双指针并不是指向同一个数组或者字符串,而是指向多个,这道题是指向两个,分别是 query 和 pattern,这种题目非常常见,能够识别和掌握这种题目的解题模板非常重要。对 queries 的每一项我们的逻辑是一样的,这里就以其中一项为例进行讲解。
以 query 为 FooBar,pattern 为 FB 为例。
首先我们来简化一下问题,假如我们没有可以在任何位置插入每个字符,也可以插入 0 个字符。这个规则。我们的问题会比较简单,这个时候我们的算法是什么样的呢?一起来看下:
  1. 1.
    首先我们建立两个指针 i 和 j 分别指向 query 和 pattern 的首字母。
  2. 2.
    当 i 和 j 指向的字母相同的时候,我们同时向后移动两个指针一个单位。
  3. 3.
    当 i 和 j 指向的字母不同的时候,我们直接返回 False
假如我们要找到的不是子串,而是子序列怎么办?我们不妨假设判断 pattern 是否是 query 的子序列。 其实 LeetCode 实际上也有这样的题目,我们来看下:
  1. 1.
    首先我们建立两个指针 i 和 j 分别指向 query 和 pattern 的首字母。
  2. 2.
    当 i 和 j 指向的字母相同的时候,我们同时向后移动两个指针一个单位。
  3. 3.
    当 i 和 j 指向的字母不同的时候,我们移动 i 指针。
  4. 4.
    当 i 超出 query 范围的时候,我们只需要判断 pattern 是否达到了终点即可。当然我们也可以提前退出。
我们直接参考下 LeetCode 392. 判断子序列
代码:
给定字符串 s 和 t ,判断 s 是否为 t 的子序列
Python Code:
1
class Solution:
2
def isSubsequence(self, s: str, t: str) -> bool:
3
i = 0
4
j = 0
5
while j < len(t):
6
if i < len(s) and s[i] == t[j]:
7
i += 1
8
j += 1
9
else:
10
j += 1
11
if i >= len (s):
12
return True
13
return i == len(s)
Copied!
然后我们加上可以在任何位置插入每个字符,也可以插入 0 个字符。这个规则。来看下有什么不同:
  1. 1.
    首先我们建立两个指针 i 和 j 分别指向 query 和 pattern 的首字母。
  2. 2.
    当 i 和 j 指向的字母相同的时候,我们同时向后移动两个指针一个单位。
  3. 3.
    当 i 和 j 指向的字母不同的时候,我们继续判断 i 指向的元素是否是小写。
  4. 4.
    如果是小写我们只把 i 向后移动一个单位。
  5. 5.
    如果不是小写我们直接返回 False

关键点解析

  • 双指针
  • 字符串匹配
  • 子序列
  • 子串

代码

Python Code:
1
class Solution:
2
def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:
3
res = []
4
for query in queries:
5
i = 0
6
j = 0
7
while i < len(query):
8
if j < len(pattern) and query[i] == pattern[j]:
9
i += 1
10
j += 1
11
elif query[i].islower():
12
i += 1
13
else:
14
break
15
if i == len(query) and j == len(pattern):
16
res.append(True)
17
else:
18
res.append(False)
19
return res
Copied!
复杂度分析
其中 N 为 queries 的长度, M 为 queries 的平均长度, P 为 pattern 的长度。
  • 时间复杂度:$O(N M P)$
  • 空间复杂度:$O(1)$

扩展

这是一个符合直觉的解法,但是却不是一个很优秀的解法,那么你有想到什么优秀的解法么?

参考