208. 实现 Trie

题目描述

前缀树（Trie）是一种树形结构，能高效地保存和查找一组字符串，常用于自动补全、拼写检查等场景。

实现 Trie 类： - Trie()：创建一棵空的前缀树。 - insert(word)：把字符串 word 存进树中。 - search(word)：返回布尔值。若 word 之前被完整插入过，返回 true，否则返回 false。 - startsWith(prefix)：返回布尔值。若已插入的字符串中有某一个以 prefix 开头，返回 true，否则返回 false。

示例 1

输入：操作 = ["Trie","insert","search","search","startsWith","insert","search"]
参数 = [[],["apple"],["apple"],["app"],["app"],["app"],["app"]]
输出：[null,null,true,false,true,null,true]

解释：插入 "apple" 后，"app" 只是前缀而不是完整单词，所以 search 为 false、startsWith 为 true；再插入 "app" 后，search("app") 变为 true。

数据范围

1 <= word.length, prefix.length <= 2000
word 和 prefix 只含小写英文字母。
insert、search、startsWith 合计调用不超过 3 * 10^4 次。

解题思路

按字符沿子节点边查找。

为什么正确

节点只表示已经匹配的前缀。

复杂度分析

插入和查询的时间均为 O(L)，额外空间 O(总字符数·|Σ|)。

易错点

注意边界条件并在回溯或弹出后恢复状态。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Node:
 def __init__(self):self.children={};self.word=False
class Trie:
 def __init__(self):self.root=Node()
 def insert(self,w):
  x=self.root
  for c in w:x=x.children.setdefault(c,Node())
  x.word=True
 def _find(self,w):
  x=self.root
  for c in w:
   if c not in x.children:return None
   x=x.children[c]
  return x
 def search(self,w):
  x=self._find(w);return x is not None and x.word
 def startsWith(self,w):return self._find(w) is not None

class Node {
    Map<Character, Node> children = new HashMap<>(); boolean word = false;
}

class Trie {
    private final Node root;

    public Trie() { root = new Node(); }

    public void insert(String w) {
        Node x = root;
        for (char c : w.toCharArray()) x = x.children.computeIfAbsent(c, k -> new Node());
        x.word = true;
    }

    private Node find(String w) {
        Node x = root;
        for (char c : w.toCharArray()) {
            if (!x.children.containsKey(c)) return null;
            x = x.children.get(c);
        }
        return x;
    }

    public boolean search(String w) {
        Node x = find(w); return x != null && x.word;
    }

    public boolean startsWith(String w) { return find(w) != null; }
}

struct Node {
    unordered_map<char, Node*> children; bool word = false;
};

class Trie {
    Node* root;

    Node* find(const string& w) {
        Node* x = root;
        for (char c : w) {
            if (!x->children.count(c)) return nullptr;
            x = x->children[c];
        }
        return x;
    }

public:
    Trie() : root(new Node()) {}

    void insert(string w) {
        Node* x = root;
        for (char c : w) {
            if (!x->children.count(c)) x->children[c] = new Node();
            x = x->children[c];
        }
        x->word = true;
    }

    bool search(string w) {
        Node* x = find(w); return x != nullptr && x->word;
    }

    bool startsWith(string w) {
        return find(w) != nullptr;
    }
};

type Node struct {
	children map[byte]*Node
	word     bool
}

type Trie struct {
	root *Node
}

func Constructor() Trie { return Trie{&Node{children: map[byte]*Node{}}} }

func (this *Trie) Insert(w string) {
	x := this.root
	for i := 0; i < len(w); i++ {
		c := w[i]
		if x.children[c] == nil {
			x.children[c] = &Node{children: map[byte]*Node{}}
		}
		x = x.children[c]
	}
	x.word = true
}

func (this *Trie) find(w string) *Node {
	x := this.root
	for i := 0; i < len(w); i++ {
		c := w[i]
		if x.children[c] == nil {
			return nil
		}
		x = x.children[c]
	}
	return x
}

func (this *Trie) Search(w string) bool {
	x := this.find(w); return x != nil && x.word
}

func (this *Trie) StartsWith(w string) bool { return this.find(w) != nil }

class Node {
    constructor() { this.children = new Map(); this.word = false; }
}

var Trie = function() { this.root = new Node(); };

Trie.prototype.insert = function(w) {
    let x = this.root;
    for (const c of w) {
        if (!x.children.has(c)) x.children.set(c, new Node());
        x = x.children.get(c);
    }
    x.word = true;
};

Trie.prototype._find = function(w) {
    let x = this.root;
    for (const c of w) {
        if (!x.children.has(c)) return null;
        x = x.children.get(c);
    }
    return x;
};

Trie.prototype.search = function(w) {
    const x = this._find(w); return x !== null && x.word;
};

Trie.prototype.startsWith = function(w) { return this._find(w) !== null; };

class Node {
    children = new Map<string, Node>(); word = false;
}

class Trie {
    private root: Node;

    constructor() { this.root = new Node(); }

    insert(w: string): void {
        let x = this.root;
        for (const c of w) {
            if (!x.children.has(c)) x.children.set(c, new Node());
            x = x.children.get(c)!;
        }
        x.word = true;
    }

    private find(w: string): Node | null {
        let x = this.root;
        for (const c of w) {
            if (!x.children.has(c)) return null;
            x = x.children.get(c)!;
        }
        return x;
    }

    search(w: string): boolean {
        const x = this.find(w); return x !== null && x.word;
    }

    startsWith(w: string): boolean { return this.find(w) !== null; }
}

载入编辑器，自己跑一遍 →

图论专题的其他题目

查看图论全部题目 →