題目描述
這是 LeetCode 上的 745. 前綴和后綴搜索 嗤朴，難度為 困難。
Tag : 「字典樹」
設(shè)計(jì)一個(gè)包含一些單詞的特殊詞典虫溜，并能夠通過前綴和后綴來(lái)檢索單詞雹姊。
實(shí)現(xiàn) WordFilter 類：
-
WordFilter(string[] words)使用詞典中的單詞words初始化對(duì)象。 -
f(string pref, string suff)返回詞典中具有前綴prefix和后綴suff的單詞的下標(biāo)衡楞。如果存在不止一個(gè)滿足要求的下標(biāo)吱雏，返回其中 最大的下標(biāo) 。如果不存在這樣的單詞寺酪，返回坎背。
示例：
輸入
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
輸出
[null, 0]
解釋
WordFilter wordFilter = new WordFilter(["apple"]);
wordFilter.f("a", "e"); // 返回 0 ，因?yàn)橄聵?biāo)為 0 的單詞：前綴 prefix = "a" 且 后綴 suff = "e" 寄雀。
提示：
-
words[i]、pref和suff僅由小寫英文字母組成 - 最多對(duì)函數(shù)
f執(zhí)行次調(diào)用
基本分析
為了方便陨献，我們令 words 為 ss盒犹，令 pref 和 suff 分別為 a 和 b。
搜索某個(gè)前綴（后綴可看做是反方向的前綴）容易想到字典樹眨业，但單詞長(zhǎng)度數(shù)據(jù)范圍只有 急膀，十分具有迷惑性，使用暴力做法最壞情況下會(huì)掃描所有的
龄捡，不考慮任何的剪枝操作的話卓嫂，計(jì)算量也才為
，按道理是完全可以過的聘殖。
但不要忘記 LC 是一個(gè)具有「設(shè)定每個(gè)樣例時(shí)長(zhǎng)晨雳，同時(shí)又有總時(shí)長(zhǎng)」這樣奇怪機(jī)制的 OJ行瑞。
暴力（TLE or 雙百)
于是有了 Java 總時(shí)間超時(shí)，TypeScripe 雙百的結(jié)果（應(yīng)該是 TypeScript 提交不多餐禁，同時(shí)設(shè)限寬松的原因）：
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
}
}
- 時(shí)間復(fù)雜度：初始化操作復(fù)雜度為
血久，檢索操作復(fù)雜度為
- 空間復(fù)雜度：
Trie
使用字典樹優(yōu)化檢索過程也是容易的，分別使用兩棵 Trie 樹來(lái)記錄 的前后綴帮非，即正著存到
tr1 中氧吐，反著存到 Tr2 中。
還不了解
Trie的同學(xué)可以先看前置 ??：【設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)】實(shí)現(xiàn) Trie (前綴樹)
前置 ?? 通過圖解形式講解了Trie的結(jié)構(gòu)與原理末盔，以及提供了兩種實(shí)現(xiàn)Trie的方式
同時(shí)對(duì)于字典樹的每個(gè)節(jié)點(diǎn)筑舅，我們使用數(shù)組 idxs 記錄經(jīng)過該節(jié)點(diǎn)的字符串 所在
ss 中的下標(biāo) ，若某個(gè)字典樹節(jié)點(diǎn)的索引數(shù)組
tr.idxs 為 則代表「從根節(jié)點(diǎn)到
tr 節(jié)點(diǎn)所對(duì)應(yīng)的字符串」為 的前綴陨舱。
這樣我們可以即可在掃描前后綴 a 和 b 時(shí)翠拣，得到對(duì)應(yīng)的候選下標(biāo)列表 l1 和 l2，由于我們將 添加到兩棵
tr 中是按照下標(biāo)「從小到大」進(jìn)行隅忿，因此我們使用「雙指針」算法分別從 l1 和 l2 結(jié)尾往后找到第一個(gè)共同元素即是答案（滿足條件的最大下標(biāo)）心剥。
使用
Trie優(yōu)化后，Java從TLE到AC背桐，TypeScript耗時(shí)為原本的：
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);
}
};
- 時(shí)間復(fù)雜度：初始化操作復(fù)雜度為
兽肤，檢索過程復(fù)雜度為
，其中
為前后綴的最大長(zhǎng)度啃炸，
為初始化數(shù)組長(zhǎng)度谐算，代表最多有
個(gè)候選下標(biāo)（注意：這里的
励饵，如果要將
的話驳癌，需要將兩個(gè)候選集設(shè)計(jì)成交替下標(biāo)，此時(shí)
f如果仍是map記錄查詢次數(shù)來(lái)進(jìn)行優(yōu)化） - 空間復(fù)雜度：
最后
這是我們「刷穿 LeetCode」系列文章的第 No.745 篇，系列開始于 2021/01/01典予，截止于起始日 LeetCode 上共有 1916 道題目甜滨，部分是有鎖題，我們將先把所有不帶鎖的題目刷完瘤袖。
在這個(gè)系列文章里面衣摩，除了講解解題思路以外，還會(huì)盡可能給出最為簡(jiǎn)潔的代碼捂敌。如果涉及通解還會(huì)相應(yīng)的代碼模板艾扮。
為了方便各位同學(xué)能夠電腦上進(jìn)行調(diào)試和提交代碼既琴，我建立了相關(guān)的倉(cāng)庫(kù)：https://github.com/SharingSource/LogicStack-LeetCode 。
在倉(cāng)庫(kù)地址里栏渺，你可以看到系列文章的題解鏈接呛梆、系列文章的相應(yīng)代碼、LeetCode 原題鏈接和其他優(yōu)選題解磕诊。
更多更全更熱門的「筆試/面試」相關(guān)資料可訪問排版精美的 合集新基地 ????
本文由mdnice多平臺(tái)發(fā)布
