Finding in a Trie

Now, let's search for a word in a Trie:

  1. Consider the current node as the root.
  2. Loop the given word character by character (start from the first character).
  3. For each character, check its presence in the Trie (in Map<Character, Node>).
  4. If a character is not present, then return false.
  5. Repeat from step 2 until the end of the word.
  6. 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.
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
18.226.170.187