# 1023. 驼峰式匹配

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

<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
```

**复杂度分析**

其中 N 为 queries 的长度， M 为 queries 的平均长度， P 为 pattern 的长度。

* 时间复杂度：$O(N *M* P)$
* 空间复杂度：$O(1)$

## 扩展

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

## 参考

* [392. 判断子序列](https://leetcode-cn.com/problems/is-subsequence/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1023.camelcase-matching.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.