Now, let's search for a word in a Trie:
- Consider the current node as the root.
- Loop the given word character by character (start from the first character).
- For each character, check its presence in the Trie (in Map<Character, Node>).
- If a character is not present, then return false.
- Repeat from step 2 until the end of the word.
- At the end of the word, return true if this was a word, or false if it was just a prefix.
In terms of code lines, we have the following:
public boolean contains(String word) {
Node node = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
node = node.getChildren().get(ch);
if (node == null) {
return false;
}
}
return node.isWord();
}
The complexity of finding is O(n), where n represents the word size.