137 lines
5.0 KiB
Markdown
137 lines
5.0 KiB
Markdown
|
## 题目地址
|
|||
|
|
|
|||
|
|
https://leetcode-cn.com/problems/camelcase-matching/
|
|||
|
|
|
|||
|
|
## 题目描述
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
如果我们可以将小写字母插入模式串 pattern 得到待查询项 query，那么待查询项与给定模式串匹配。（我们可以在任何位置插入每个字符，也可以插入 0 个字符。）
|
|||
|
|
|
|||
|
|
给定待查询列表 queries，和模式串 pattern，返回由布尔值组成的答案列表 answer。只有在待查项 queries[i] 与模式串 pattern 匹配时， answer[i] 才为 true，否则为 false。
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
示例 1：
|
|||
|
|
|
|||
|
|
输入：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".
|
|||
|
|
示例 2：
|
|||
|
|
|
|||
|
|
输入：queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBa"
|
|||
|
|
输出：[true,false,true,false,false]
|
|||
|
|
解释：
|
|||
|
|
"FooBar" 可以这样生成："Fo" + "o" + "Ba" + "r".
|
|||
|
|
"FootBall" 可以这样生成："Fo" + "ot" + "Ba" + "ll".
|
|||
|
|
示例 3：
|
|||
|
|
|
|||
|
|
输出：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
|
|||
|
|
所有字符串都仅由大写和小写英文字母组成。
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
## 思路
|
|||
|
|
|
|||
|
|
这道题是一道典型的双指针题目。不过这里的双指针并不是指向同一个数组或者字符串，而是指向多个，这道题是指向两个，分别是 query 和 pattern，这种题目非常常见，能够识别和掌握这种题目的解题模板非常重要。对 queries 的每一项我们的逻辑是一样的，这里就以其中一项为例进行讲解。
|
|||
|
|
|
|||
|
|
以 query 为 FooBar，pattern 为 FB 为例。
|
|||
|
|
|
|||
|
|
首先我们来简化一下问题，假如我们没有`可以在任何位置插入每个字符，也可以插入 0 个字符。`这个规则。我们的问题会比较简单，这个时候我们的算法是什么样的呢？一起来看下：
|
|||
|
|
|
|||
|
|
1. 首先我们建立两个指针 i 和 j 分别指向 query 和 pattern 的首字母。
|
|||
|
|
2. 当 i 和 j 指向的字母相同的时候，我们同时向后移动两个指针一个单位。
|
|||
|
|
3. 当 i 和 j 指向的字母不同的时候，我们直接返回 False
|
|||
|
|
|
|||
|
|
假如我们要找到的不是子串，而是子序列怎么办？我们不妨假设判断 pattern 是否是 query 的子序列。 其实 LeetCode 实际上也有这样的题目，我们来看下：
|
|||
|
|
|
|||
|
|
1. 首先我们建立两个指针 i 和 j 分别指向 query 和 pattern 的首字母。
|
|||
|
|
2. 当 i 和 j 指向的字母相同的时候，我们同时向后移动两个指针一个单位。
|
|||
|
|
3. 当 i 和 j 指向的字母不同的时候，我们移动 i 指针。
|
|||
|
|
4. 当 i 超出 query 范围的时候，我们只需要判断 pattern 是否达到了终点即可。当然我们也可以提前退出。
|
|||
|
|
|
|||
|
|
我们直接参考下 LeetCode [392. 判断子序列](https://leetcode-cn.com/problems/is-subsequence/)。
|
|||
|
|
|
|||
|
|
代码：
|
|||
|
|
|
|||
|
|
> 给定字符串 s 和 t ，判断 s 是否为 t 的子序列
|
|||
|
|
|
|||
|
|
Python Code:
|
|||
|
|
|
|||
|
|
```python
|
|||
|
|
class Solution:
|
|||
|
|
def isSubsequence(self, s: str, t: str) -> bool:
|
|||
|
|
i = 0
|
|||
|
|
j = 0
|
|||
|
|
while j < len(t):
|
|||
|
|
if i < len(s) and s[i] == t[j]:
|
|||
|
|
i += 1
|
|||
|
|
j += 1
|
|||
|
|
else:
|
|||
|
|
j += 1
|
|||
|
|
if i >= len (s):
|
|||
|
|
return True
|
|||
|
|
return i == len(s)
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
然后我们加上`可以在任何位置插入每个字符，也可以插入 0 个字符。`这个规则。来看下有什么不同：
|
|||
|
|
|
|||
|
|
1. 首先我们建立两个指针 i 和 j 分别指向 query 和 pattern 的首字母。
|
|||
|
|
2. 当 i 和 j 指向的字母相同的时候，我们同时向后移动两个指针一个单位。
|
|||
|
|
3. 当 i 和 j 指向的字母不同的时候，我们继续判断 i 指向的元素是否是小写。
|
|||
|
|
4. 如果是小写我们只把 i 向后移动一个单位。
|
|||
|
|
5. 如果不是小写我们直接返回 False
|
|||
|
|
|
|||
|
|
## 关键点解析
|
|||
|
|
|
|||
|
|
- 双指针
|
|||
|
|
- 字符串匹配
|
|||
|
|
- 子序列
|
|||
|
|
- 子串
|
|||
|
|
|
|||
|
|
## 代码
|
|||
|
|
|
|||
|
|
Python Code:
|
|||
|
|
|
|||
|
|
```python
|
|||
|
|
class Solution:
|
|||
|
|
def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:
|
|||
|
|
res = []
|
|||
|
|
for query in queries:
|
|||
|
|
i = 0
|
|||
|
|
j = 0
|
|||
|
|
while i < len(query):
|
|||
|
|
if j < len(pattern) and query[i] == pattern[j]:
|
|||
|
|
i += 1
|
|||
|
|
j += 1
|
|||
|
|
elif query[i].islower():
|
|||
|
|
i += 1
|
|||
|
|
else:
|
|||
|
|
break
|
|||
|
|
if i == len(query) and j == len(pattern):
|
|||
|
|
res.append(True)
|
|||
|
|
else:
|
|||
|
|
res.append(False)
|
|||
|
|
return res
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
## 扩展
|
|||
|
|
|
|||
|
|
这是一个符合直觉的解法，但是却不是一个很优秀的解法，那么你有想到什么优秀的解法么？
|
|||
|
|
|
|||
|
|
## 参考
|
|||
|
|
|
|||
|
|
- [392. 判断子序列](https://leetcode-cn.com/problems/is-subsequence/)
|