Mediumtrie
Implement Trie (Prefix Tree)
Problem (yeniden ifade)
insert, search (tam kelime) ve startsWith (önek) ile Trie uygula.
Sezgi
Her düğümde children map/dizi; kelime-sonu bayrağı.
Yaklaşımlar
Trie insert/search/startsWith
DoğrulanmadıZaman O(L) per opAlan O(Σ L)
Fikir. her karakter için kenarları yürü; insert’te oluştur; search end bayrağı ister.
Yürüyüş. insert apple; search apple true; search app false; startsWith app true.
Trade-off. Array[26] küçük harf için en hızlı; map genelleştirir.
Çözüm
class TrieNode {
children: Map<string, TrieNode> = new Map();
end = false;
}
export class Trie {
private root = new TrieNode();
insert(word: string): void {
let n = this.root;
for (const c of word) {
if (!n.children.has(c)) n.children.set(c, new TrieNode());
n = n.children.get(c)!;
}
n.end = true;
}
search(word: string): boolean {
const n = this.walk(word);
return !!n && n.end;
}
startsWith(prefix: string): boolean {
return !!this.walk(prefix);
}
private walk(s: string): TrieNode | null {
let n = this.root;
for (const c of s) {
if (!n.children.has(c)) return null;
n = n.children.get(c)!;
}
return n;
}
}
class TrieNode {
children: Map<string, TrieNode> = new Map();
end = false;
}
export class Trie {
private root = new TrieNode();
insert(word: string): void {
let n = this.root;
for (const c of word) {
if (!n.children.has(c)) n.children.set(c, new TrieNode());
n = n.children.get(c)!;
}
n.end = true;
}
search(word: string): boolean {
const n = this.walk(word);
return !!n && n.end;
}
startsWith(prefix: string): boolean {
return !!this.walk(prefix);
}
private walk(s: string): TrieNode | null {
let n = this.root;
for (const c of s) {
if (!n.children.has(c)) return null;
n = n.children.get(c)!;
}
return n;
}
}
Şablon bağlantısı
Trie şablon iskeleti.
Yansıma
searchkelime bitiş bayrağı ister.startsWithyürüyüşün kopmaması yeter.- Eksik harf yok. Boş kelime kökün bayrağı. Aynı kelimeyi iki kez eklemek bir kez sayılır.
- Çocuk harf başına. 26’lık dizi sık alfabe, map seyrek alfabe.