解題說明
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 也可以包含小寫字母的通配符,匹配規則會怎麼變?
- 如果查詢字串中允許刪除字母(而不只是插入),問題如何變化?
- 如何高效地處理大量查詢(例如百萬級),可以做哪些預處理?