1023. 駝峰式匹配 · ttttt

# 1023. 駝峰式匹配 ## 題目地址(1023. 駝峰式匹配) <https://leetcode-cn.com/problems/camelcase-matching/> ## 題目描述 ``` <pre class="calibre18">``` 如果我們可以將小寫字母插入模式串 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: ``` <pre class="calibre18">``` 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: ``` <pre class="calibre18">``` 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(N \* M \* P)O(N?M?P) - 空間復雜度：O(1)O(1)O(1) ## 擴展這是一個符合直覺的解法，但是卻不是一個很優秀的解法，那么你有想到什么優秀的解法么？ ## 參考 - [392. 判斷子序列](https://leetcode-cn.com/problems/is-subsequence/)