208. Implement Trie (Prefix Tree)

LeetCode 208. Implement Trie (Prefix Tree)

Description

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie() Initializes the trie object.

• void insert(String word) Inserts the string word into the trie.

• boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.

• boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

Constraints:

• 1 <= word.length, prefix.length <= 2000

• word and prefix consist only of lowercase English letters.

• At most 3 * 10^4 calls in total will be made to insert, search, and startsWith.

Tags

Design, Trie

Solution

Properties

• children [26]*Trie: an array of pointers to children Trie nodes;

• isEnd bool: a flag indicates if this node is the last character of a stored string.

Insert

We assign a pointer to the root to search. For each character of the input word, if this character exists in the children array of the current node, we move the pointer to that child; otherwise we create a child node. At last, we set the pointer's isEnd = true.

Search Prefix

This method returns the last node if the prefix exists. If the character does not exist, return nil.

Complexity

• Time complexity: $O(n)$

• Space complexity: $O(n)$

Code

type Trie struct {
	children [26]*Trie
	isEnd    bool
}

// Constructor initializee your data structure here.
func Constructor() Trie {
	return Trie{}
}

// Insert inserts a word into the trie.
func (t *Trie) Insert(word string) {
	p := t
	for _, ch := range word {
		ch -= 'a'
		if p.children[ch] == nil {
			p.children[ch] = &Trie{}
		}
		p = p.children[ch]
	}
	p.isEnd = true
}

func (t *Trie) searchPrefix(word string) *Trie {
	p := t
	for _, ch := range word {
		ch -= 'a'
		if p.children[ch] == nil {
			return nil
		}
		p = p.children[ch]
	}
	return p
}

// Search returns if the word is in the trie.
func (t *Trie) Search(word string) bool {
	node := t.searchPrefix(word)
	return node != nil && node.isEnd == true
}

// StartsWith returns if there is any word in the trie that starts with the given prefix.
func (t *Trie) StartsWith(prefix string) bool {
	return t.searchPrefix(prefix) != nil
}

Reference

1. 实现 Trie（前缀树）