題目描述:設計 WordFilter,建構時傳入單詞陣列 words,支援查詢 f(pref, suff):回傳同時擁有前綴 pref 且後綴為 suff 的單詞在陣列中的最大索引;若不存在則回傳 -1。單詞可重複(取最大索引)。
解題思路:核心觀察是:若將後綴與前綴組合成 suff + '#' + word,並在 HashMap 中以此字串為鍵儲存索引,則查詢 f(pref, suff) 只需查鍵 suff + '#' + pref 是否以其作為前綴——但最直接的版本是直接以完整的 suff + '#' + word 為鍵存 HashMap,查詢 suff + '#' + pref 並不是前綴查詢而是完整鍵。
更簡單的 HashMap 版本:對每個 words[i],枚舉其所有後綴 s(含空串),對每個後綴 s 再枚舉所有前綴 p(含空串),以 s + '#' + p 為鍵存入 HashMap,值為索引 i(後來的覆蓋前面的,天然取最大索引)。查詢 f(pref, suff) 時直接查 suff + '#' + pref。
複雜度分析:預處理時每個字串長度為 L,後綴有 L+1 個,前綴有 L+1 個,故每個字串產生 O(L²) 個鍵;所有字串總計 O(N × L²) 個鍵,每鍵長度 O(L),空間 O(N × L³)。查詢 O(pref_len + suff_len)。此法以空間換時間,適合查詢遠多於建構的場景。
時間複雜度:建構 O(N × L³)(N 個字串,每個長 L,O(L²) 個鍵,每鍵長 O(L));f 查詢 O(|pref| + |suff|)(雜湊計算與查找)。
空間複雜度:O(N × L³) — HashMap 儲存所有 (suff, pref) 組合的鍵字串。題目限制 N ≤ 104、L ≤ 7,實際最大空間約 10⁴ × 7³ ≈ 3.4 × 10⁶ 個字元,可接受。
Constructor(words):
1. For i = 0 to len(words)-1:
w = words[i], L = len(w)
For si = 0 to L: // enumerate all suffixes
suff = w[si..L-1]
For pi = 0 to L: // enumerate all prefixes
pref = w[0..pi-1] // (empty string when pi=0)
key = suff + '#' + pref
lookup[key] = i // overwrite with larger index
f(pref, suff):
1. key = suff + '#' + pref
2. If key in lookup: return lookup[key]
3. Return -1雙 Trie(前綴 Trie + 後綴 Trie)+ 集合交集:分別建前綴 Trie 和後綴 Trie,每個節點儲存含有此前/後綴的所有詞索引集合。查詢時取兩集合的交集最大值。空間 O(N × L × 26),查詢需要交集運算 O(N),建構 O(N × L²)。適合字串長度大但查詢少的情況。
Trie with pair encoding:建單一 Trie,鍵為 suff + '#' + pref(與 HashMap 版相同),但用 Trie 儲存以支援前綴搜尋擴展。空間與 HashMap 版相近但支援「前綴 pref 的所有結果」類查詢,提供更強的擴展性。
離線排序 + 二分搜尋:預處理時對所有 (word, idx) 按照字典序排列前綴和後綴兩個有序陣列,查詢時分別二分搜尋找出前綴和後綴的索引集合再取最大交集。時間 O(N × L × log(N × L)) 建構,O(L × log(N × L) + result_size) 查詢。
# 作為分隔符在純小寫字母場景是安全的?