Skip to main content

208. Implement Trie (Prefix Tree)

https://leetcode.com/problems/implement-trie-prefix-tree/

Python​

With custom TrieNode class​

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        cur = self.root
        for char in word:
            if char not in cur.children:
                cur.children[char] = TrieNode()
            cur = cur.children[char]
        cur.is_end = True

    def search(self, word: str) -> bool:
        cur = self.root
        for char in word:
            if char not in cur.children:
                return False
            cur = cur.children[char]
        return cur.is_end

    def startsWith(self, prefix: str) -> bool:
        cur = self.root
        for char in prefix:
            if char not in cur.children:
                return False
            cur = cur.children[char]
        return True

Native Dict with custom EOS (End-of-string) sign​

class Trie(object):
    EOS = '-'
    def __init__(self):
        self.root = {}

    def insert(self, word):
        cur = self.root
        for char in word:
            if char not in cur:
                cur[char] = {}
            cur = cur[char]
        cur[self.EOS] = True

    def search(self, word):
        cur = self.root
        for char in word:
            if char not in cur:
                return False
            cur = cur[char]
        return self.EOS in cur

    def startsWith(self, prefix):
        cur = self.root
        for char in prefix:
            if char not in cur:
                return False
            cur = cur[char]
        return True

Javascript​

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

/**
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function (word) {
	let node = this.root;

	for (const char of word) {
		if (!node[char]) {
			node[char] = {};
		}
		node = node[char];
	}
	node.isWord = true;
};

/**
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function (word) {
	let node = this.root;

	for (const char of word) {
    if (!node[char]) return false
		node = node[char];
	}

	return node.isWord ?? false;
};

/**
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function (prefix) {
	let node = this.root;

	for (const char of prefix) {
    if (!node[char]) return false
		node = node[char];
	}

	return true;
};