解題說明
Camelcase Matching
題目描述： 給定一組查詢字串 queries 和一個模式 pattern。對每個查詢，判斷能否在 pattern 中的字母之間插入小寫字母來得到該查詢。換言之，查詢字串必須包含 pattern 作為子序列，且查詢中不在 pattern 中的字母必須都是小寫的。
解題思路：
- 雙指標：對每個查詢，用兩個指標分別遍歷查詢字串和 pattern。
- 如果查詢中當前字元匹配 pattern 當前字元，兩個指標都前進。
- 如果不匹配且查詢中當前字元是大寫字母，則匹配失敗（多餘的大寫字母無法插入 pattern）。
- 如果不匹配且是小寫字母，只移動查詢的指標（這個小寫字母是插入的）。
- 最終 pattern 的指標必須到達末尾（pattern 被完全匹配）。
C++ 解法
複雜度分析
時間複雜度：O(q * (n + m)) — q 為查詢數，n 為查詢長度，m 為 pattern 長度
空間複雜度：O(1) — 不計輸出的額外空間
虛擬碼
1. For each query in queries:
a. Initialize pattern pointer j = 0
b. For each character c in query:
- If j < pattern.length and c == pattern[j]: advance j
- Else if c is uppercase: mark as not matching, break
c. Query matches if j == pattern.length
2. Return list of match results其他解法
-
Trie 方法：建立一個 Trie 存儲所有可能的展開形式。但由於可插入的小寫字母組合太多，這不實際。Trie 更適合多個 pattern 匹配同一查詢的場景。
-
正則表達式：將 pattern 轉換成正則：在每個字元之間插入
[a-z]*。用正則引擎匹配。概念清晰但效率較差，且面試中通常期待手動實作。
延伸思考
- 如果 pattern 也可以包含小寫字母的通配符，匹配規則會怎麼變？
- 如果查詢字串中允許刪除字母（而不只是插入），問題如何變化？
- 如何高效地處理大量查詢（例如百萬級），可以做哪些預處理？