Trie

O(n)
n = length(string)

Python | Java

	class TrieNode:
	def __init__(self):
	self.isWord = False
	self.nodes = {}
	class Trie:
	def __init__(self):
	self.root = TrieNode()
	# Inserts a word into the trie.
	def insert(self, word: str) -> None:
	cur = self.root;
	for c in word:
	if c not in cur.nodes:
	cur.nodes[c] = TrieNode()
	cur = cur.nodes[c]
	cur.isWord = True;
	# Returns if the word is in the trie
	def search(self, word: str) -> bool:
	cur = self.root
	for c in word:
	if c not in cur.nodes:
	return False
	cur = cur.nodes[c]
	return cur.isWord
	# Returns if there is any word in the trie
	# that starts with the given prefix. */
	def startsWith(self, prefix: str) -> bool:
	cur = self.root
	for c in prefix:
	if c not in cur.nodes:
	return False
	cur = cur.nodes[c]
	return True

view raw Trie.py hosted with ❤ by GitHub

	class Trie {
	private class TrieNode {
	public boolean isWord = false
	public TrieNode[] nodes = new TrieNode[26];
	}
	TrieNode root = new TrieNode();
	/** Inserts a word into the trie. */
	public void insert(String word) {
	TrieNode cur = root;
	for (int i = 0; i < word.length(); i++) {
	char c = word.charAt(i);
	int index = c - 'a';
	if (cur.nodes[index] == null) cur.nodes[index] = new TrieNode();
	cur = cur.nodes[index];
	}
	cur.isWord = true;
	}
	/** Returns if the word is in the trie. */
	public boolean search(String word) {
	TrieNode cur = root;
	for (int i = 0; i < word.length(); i++) {
	char c = word.charAt(i);
	int index = c - 'a';
	if (cur.nodes[index] == null) return false;
	cur = cur.nodes[index];
	}
	return cur.isWord;
	}
	/** Returns if there is any word in the trie
	that starts with the given prefix. */
	public boolean startsWith(String prefix) {
	TrieNode cur = root;
	for (int i = 0; i < prefix.length(); i++) {
	char c = prefix.charAt(i);
	int index = c - 'a';
	if (cur.nodes[index] == null) return false;
	cur = cur.nodes[index];
	}
	return true;
	}
	}

view raw Trie.java hosted with ❤ by GitHub