Leetcode Problem 1804. Implement Trie II (Prefix Tree)

1804. Implement Trie II (Prefix Tree)

Leetcode Solutions

Enhanced Trie with Counters

  1. Define a TrieNode class with an array for children nodes, words_ending_here, and words_starting_here counters.
  2. Implement the insert method to traverse the Trie, creating nodes as necessary, incrementing words_starting_here at each node along the path, and incrementing words_ending_here at the final node.
  3. Implement countWordsEqualTo by traversing the Trie following the word's characters and returning the words_ending_here counter of the last node.
  4. Implement countWordsStartingWith by traversing the Trie following the prefix's characters and returning the words_starting_here counter of the last node.
  5. Implement erase by traversing the Trie, decrementing words_starting_here at each node along the path, and decrementing words_ending_here at the final node.
UML Thumbnail

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...