Trie

Tree data structure that stores a dynamic set of strings, making it easy to search for a string in the set.

class Trie

Bases: object

Trie (prefix tree) implementation. Trie is a tree-like data structure whose nodes store the letters of an alphabet by structuring the nodes in a particular way, words and strings can be retrieved from the structure by traversing down a branch path of the tree.

No node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated.

All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string.

Values are not necessarily associated with every node.

Rather, values tend only to be associated with leaves, and with some inner nodes that correspond to keys of interest.

insert(word: str) → None

Inserts a word into the trie.

Time complexity: \(O(n)\), where n is the length of the word.

Return type:

None

search(word: str) → bool

Returns if the word is in the trie.

Time complexity: \(O(n)\), where n is the length of the word.

Return type:

bool

startsWith(prefix: str) → bool

Returns if there is any word in the trie that starts with the given prefix.

Time complexity: \(O(n)\), where n is the length of the prefix.

Return type:

bool

class TrieNode(isValid=False, val='')

Bases: object

Trie Node