【面試高頻題】難度 3/5，字典樹熱門運用題

題目描述

這是 LeetCode 上的 「745. 前綴和后綴搜索」 ，難度為 「困難」。

Tag : 「字典樹」

設計一個包含一些單詞的特殊詞典，并能夠通過前綴和后綴來檢索單詞。

實現 WordFilter 類：

WordFilter(string[] words) 使用詞典中的單詞 words 初始化對象。
f(string pref, string suff) 返回詞典中具有前綴? prefix?和后綴 suff?的單詞的下標。如果存在不止一個滿足要求的下標，返回其中最大的下標。如果不存在這樣的單詞，返回。

示例：

輸入
["WordFilter",?"f"]
[[["apple"]],?["a",?"e"]]

輸出
[null,?0]

解釋
WordFilter?wordFilter?=?new?WordFilter(["apple"]);
wordFilter.f("a",?"e");?//?返回?0?，因為下標為?0?的單詞：前綴?prefix?=?"a"?且?后綴?suff?=?"e"?。

提示：

words[i]、 pref 和 suff 僅由小寫英文字母組成
最多對函數 f 執行次調用

基本分析

為了方便，我們令 words 為 ss，令 pref 和 suff 分別為 a 和 b。

搜索某個前綴（后綴可看做是反方向的前綴）容易想到字典樹，但單詞長度數據范圍只有，十分具有迷惑性，使用暴力做法最壞情況下會掃描所有的，不考慮任何的剪枝操作的話，計算量也才為，按道理是完全可以過的。

但不要忘記 LC 是一個具有「設定每個樣例時長，同時又有總時長」這樣奇怪機制的 OJ。

暴力（TLE or 雙百)

于是有了 Java 總時間超時，TypeScripe 雙百的結果（應該是 TypeScript 提交不多，同時設限寬松的原因）：

Java 代碼：

class?WordFilter?{
????String[]?ss;
????public?WordFilter(String[]?words)?{
????????ss?=?words;
????}
????public?int?f(String?a,?String?b)?{
????????int?n?=?a.length(),?m?=?b.length();
????????for?(int?k?=?ss.length?-?1;?k?>=?0;?k--)?{
????????????String?cur?=?ss[k];
????????????int?len?=?cur.length();
????????????if?(len?<?n?||?len?<?m)?continue;
????????????boolean?ok?=?true;
????????????for?(int?i?=?0;?i?<?n?&&?ok;?i++)?{
????????????????if?(cur.charAt(i)?!=?a.charAt(i))?ok?=?false;
????????????}
????????????for?(int?i?=?0;?i?<?m?&&?ok;?i++)?{
????????????????if?(cur.charAt(len?-?1?-?i)?!=?b.charAt(m?-?1?-?i))?ok?=?false;
????????????}
????????????if?(ok)?return?k;
????????}
????????return?-1;
????}
}

TypeScript 代碼：

class?WordFilter?{
????ss:?string[]
????constructor(words:?string[])?{
????????this.ss?=?words
????}
????f(a:?string,?b:?string):?number?{
????????const?n?=?a.length,?m?=?b.length
????????for?(let?k?=?this.ss.length?-?1;?k?>=?0;?k--)?{
????????????const?cur?=?this.ss[k]
????????????const?len?=?cur.length
????????????if?(len?<?n?||?len?<?m)?continue
????????????let?ok?=?true
????????????for?(let?i?=?0;?i?<?n?&&?ok;?i++)?{
????????????????if?(cur[i]?!=?a[i])?ok?=?false
????????????}
????????????for?(let?i?=?m?-?1;?i?>=?0;?i--)?{
????????????????if?(cur[len?-?1?-?i]?!=?b[m?-?1?-?i])?ok?=?false
????????????}
????????????if?(ok)?return?k
????????}
????????return?-1
????}
}

時間復雜度：初始化操作復雜度為，檢索操作復雜度為
空間復雜度：

Trie

使用字典樹優化檢索過程也是容易的，分別使用兩棵 Trie 樹來記錄的前后綴，即正著存到 tr1 中，反著存到 Tr2 中。

?
還不了解 Trie 的同學可以先看前置 🧀：實現 Trie (前綴樹) 前置 🧀 通過圖解形式講解了 Trie 的結構與原理，以及提供了兩種實現 Trie 的方式
?

同時對于字典樹的每個節點，我們使用數組 idxs 記錄經過該節點的字符串所在 ss 中的下標，若某個字典樹節點的索引數組 tr.idxs 為則代表「從根節點到 tr 節點所對應的字符串」為的前綴。

這樣我們可以即可在掃描前后綴 a 和 b 時，得到對應的候選下標列表 l1 和 l2，由于我們將添加到兩棵 tr 中是按照下標「從小到大」進行，因此我們使用「雙指針」算法分別從 l1 和 l2 結尾往后找到第一個共同元素即是答案（滿足條件的最大下標）。

?
使用 Trie 優化后，Java 從 TLE 到 AC，TypeScript 耗時為原本的：
?

Java 代碼：

class?WordFilter?{
????class?TrieNode?{
????????TrieNode[]?tns?=?new?TrieNode[26];
????????List<Integer>?idxs?=?new?ArrayList<>();
????}
????void?add(TrieNode?p,?String?s,?int?idx,?boolean?isTurn)?{
????????int?n?=?s.length();
????????p.idxs.add(idx);
????????for?(int?i?=?isTurn???n?-?1?:?0;?i?>=?0?&&?i?<?n;?i?+=?isTurn???-1?:?1)?{
????????????int?u?=?s.charAt(i)?-?'a';
????????????if?(p.tns[u]?==?null)?p.tns[u]?=?new?TrieNode();
????????????p?=?p.tns[u];
????????????p.idxs.add(idx);
????????}
????}
????int?query(String?a,?String?b)?{
????????int?n?=?a.length(),?m?=?b.length();
????????TrieNode?p?=?tr1;
????????for?(int?i?=?0;?i?<?n;?i++)?{
????????????int?u?=?a.charAt(i)?-?'a';
????????????if?(p.tns[u]?==?null)?return?-1;
????????????p?=?p.tns[u];
????????}
????????List<Integer>?l1?=?p.idxs;
????????p?=?tr2;
????????for?(int?i?=?m?-?1;?i?>=?0;?i--)?{
????????????int?u?=?b.charAt(i)?-?'a';
????????????if?(p.tns[u]?==?null)?return?-1;
????????????p?=?p.tns[u];
????????}
????????List<Integer>?l2?=?p.idxs;
????????n?=?l1.size();?m?=?l2.size();
????????for?(int?i?=?n?-?1,?j?=?m?-?1;?i?>=?0?&&?j?>=?0;?)?{
????????????if?(l1.get(i)?>?l2.get(j))?i--;
????????????else?if?(l1.get(i)?<?l2.get(j))?j--;
????????????else?return?l1.get(i);
????????}
????????return?-1;
????}
????TrieNode?tr1?=?new?TrieNode(),?tr2?=?new?TrieNode();
????public?WordFilter(String[]?ss)?{
????????int?n?=?ss.length;
????????for?(int?i?=?0;?i?<?n;?i++)?{
????????????add(tr1,?ss[i],?i,?false);
????????????add(tr2,?ss[i],?i,?true);
????????}
????}
????public?int?f(String?a,?String?b)?{
????????return?query(a,?b);
????}
}

TypeScript 代碼：

class?TrieNode?{
????tns:?TrieNode[]?=?new?Array<TrieNode>()
????idxs:?number[]?=?new?Array<number>()
}
class?WordFilter?{
????add(p:?TrieNode,?s:?string,?idx:?number,?isTurn:?boolean):?void?{
????????const?n?=?s.length
????????p.idxs.push(idx)
????????for?(let?i?=?isTurn???n?-?1?:?0;?i?>=?0?&&?i?<?n;?i?+=?isTurn???-1?:?1)?{
????????????const?u?=?s.charCodeAt(i)?-?'a'.charCodeAt(0)
????????????if?(p.tns[u]?==?null)?p.tns[u]?=?new?TrieNode()
????????????p?=?p.tns[u]
????????????p.idxs.push(idx)
????????}
????}
????query(a:?string,?b:?string):?number?{
????????let?n?=?a.length,?m?=?b.length
????????let?p?=?this.tr1
????????for?(let?i?=?0;?i?<?n;?i++)?{
????????????const?u?=?a.charCodeAt(i)?-?'a'.charCodeAt(0)
????????????if?(p.tns[u]?==?null)?return?-1
????????????p?=?p.tns[u]
????????}
????????const?l1?=?p.idxs
????????p?=?this.tr2
????????for?(let?i?=?m?-?1;?i?>=?0;?i--)?{
????????????const?u?=?b.charCodeAt(i)?-?'a'.charCodeAt(0)
????????????if?(p.tns[u]?==?null)?return?-1
????????????p?=?p.tns[u]
????????}
????????const?l2?=?p.idxs
????????n?=?l1.length;?m?=?l2.length
????????for?(let?i?=?n?-?1,?j?=?m?-?1;?i?>=?0?&&?j?>=?0;?)?{
????????????if?(l1[i]?<?l2[j])?j--
????????????else?if?(l1[i]?>?l2[j])?i--
????????????else?return?l1[i]
????????}
????????return?-1
????}
????tr1:?TrieNode?=?new?TrieNode()
????tr2:?TrieNode?=?new?TrieNode()
????constructor(ss:?string[])?{
????????for?(let?i?=?0;?i?<?ss.length;?i++)?{
????????????this.add(this.tr1,?ss[i],?i,?false)
????????????this.add(this.tr2,?ss[i],?i,?true)
????????}
????}
????f(a:?string,?b:?string):?number?{
????????return?this.query(a,?b)
????}
}

C++ 代碼：

class?WordFilter?{
public:
????struct?TrieNode?{
????????TrieNode*?tns[26]?{nullptr};
????????vector<int>?idxs;
????};
????
????void?add(TrieNode*?p,?const?string&?s,?int?idx,?bool?isTurn)?{
????????int?n?=?s.size();
????????p->idxs.push_back(idx);
????????for(int?i?=?isTurn???n?-?1?:?0;?i?>=?0?&&?i?<?n;?i?+=?isTurn???-1?:?1)?{
????????????int?u?=?s[i]?-?'a';
????????????if(p->tns[u]?==?nullptr)?p->tns[u]?=?new?TrieNode();
????????????p?=?p->tns[u];
????????????p->idxs.push_back(idx);
????????}
????}
????
????int?query(const?string&?a,?const?string&?b)?{
????????int?n?=?a.size(),?m?=?b.size();
????????auto?p?=?tr1;
????????for(int?i?=?0;?i?<?n;?i++)?{
????????????int?u?=?a[i]?-?'a';
????????????if(p->tns[u]?==?nullptr)?return?-1;
????????????p?=?p->tns[u];
????????}
????????vector<int>&?l1?=?p->idxs;
????????p?=?tr2;
????????for(int?i?=?m?-?1;?i?>=?0;?i--)?{
????????????int?u?=?b[i]?-?'a';
????????????if(p->tns[u]?==?nullptr)?return?-1;
????????????p?=?p->tns[u];
????????}
????????vector<int>&?l2?=?p->idxs;
????????n?=?l1.size(),?m?=?l2.size();
????????for(int?i?=?n?-?1,?j?=?m?-?1;?i?>=?0?&&?j?>=?0;?)?{
????????????if(l1[i]?>?l2[j])?i--;
????????????else?if(l1[i]?<?l2[j])?j--;
????????????else?return?l1[i];
????????}
????????return?-1;
????}
????
????TrieNode*?tr1?=?new?TrieNode,?*tr2?=?new?TrieNode;
????WordFilter(vector<string>&?ss)?{
????????int?n?=?ss.size();
????????for(int?i?=?0;?i?<?n;?i++)?{
????????????add(tr1,?ss[i],?i,?false);
????????????add(tr2,?ss[i],?i,?true);
????????}
????}
????
????int?f(string?a,?string?b)?{
????????return?query(a,?b);
????}
};

時間復雜度：初始化操作復雜度為，檢索過程復雜度為，其中為前后綴的最大長度，為初始化數組長度，代表最多有個候選下標（注意：這里的只是粗略分析，實際上如果候選集長度越大的話，說明兩個候選集是重合度是越高的，從后往前找的過程是越快結束的，可以通過方程算出一個雙指針的理論最大比較次數，如果要將卡滿成的話，需要將兩個候選集設計成交替下標，此時 f 如果仍是次調用的話，必然會面臨大量的重復查詢，可通過引入 map 記錄查詢次數來進行優化）
空間復雜度：