題目描述: 給定一組查詢字串 queries 和一個模式 pattern。對每個查詢,判斷能否在 pattern 中的字母之間插入小寫字母來得到該查詢。換言之,查詢字串必須包含 pattern 作為子序列,且查詢中不在 pattern 中的字母必須都是小寫的。
解題思路:
時間複雜度: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 resultsTrie 方法:建立一個 Trie 存儲所有可能的展開形式。但由於可插入的小寫字母組合太多,這不實際。Trie 更適合多個 pattern 匹配同一查詢的場景。
正則表達式:將 pattern 轉換成正則:在每個字元之間插入 [a-z]*。用正則引擎匹配。概念清晰但效率較差,且面試中通常期待手動實作。