feat: Enhance Trie with New Features #617
Open
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
- Added `count_words()` to count the total number of words in the Trie. - Implemented `longest_common_prefix()` to find the longest common prefix among all words. - Added `autocomplete(prefix)` to provide autocomplete suggestions. - Implemented `bulk_insert(words)` to insert multiple words at once. - Added `clear()` method to remove all words from the Trie. - Implemented `is_empty()` to check if the Trie is empty. - Added `find_all_words()` to retrieve all stored words. - Implemented `shortest_unique_prefix(word)` to find the shortest unique prefix of a word. - Added `starts_with(prefix)` to check if any word starts with a given prefix. - Implemented `longest_word()` to find the longest word in the Trie.
Codecov ReportAll modified and coverable lines are covered by tests ✅
Additional details and impacted files@@ Coverage Diff @@
## main #617 +/- ##
=============================================
+ Coverage 97.345% 97.373% +0.027%
=============================================
Files 36 36
Lines 4445 4492 +47
=============================================
+ Hits 4327 4374 +47
Misses 118 118
🚀 New features to boost your workflow:
|
czgdp1807
requested changes
Mar 11, 2025
| if node.is_terminal: | ||
| strings.append(prefix) | ||
| for child in node._children: | ||
| _collect(node.get_child(child), prefix + child, strings) |
There was a problem hiding this comment.
A stack implementation is better than recursive one. Please revert this change.
| """ | ||
| return self.strings_with_prefix(prefix) | ||
|
|
||
| def bulk_insert(self, words: list) -> None: |
There was a problem hiding this comment.
I would recommend to support iterators in insert method only.
|
|
||
| None | ||
| """ | ||
| self.root = TrieNode() |
There was a problem hiding this comment.
Well nothing is removed here. Just the root is reset.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Enhance Trie with New Features
FIXES: #616
Description
This PR adds multiple new features to the Trie class, making it more versatile and functional. The following methods have been introduced:
count_words()) - Returns the total number of words stored in the Trie.longest_common_prefix()) - Finds the longest common prefix among all words in the Trie.autocomplete(prefix)) - Provides a list of words that match a given prefix.bulk_insert(words)) - Inserts multiple words into the Trie in a single operation.clear()) - Removes all words from the Trie, resetting it.is_empty()) - ReturnsTrueif the Trie is empty, otherwiseFalse.find_all_words()) - Retrieves all words currently stored in the Trie.shortest_unique_prefix(word)) - Determines the shortest unique prefix for a given word.starts_with(prefix)) - ReturnsTrueif any word in the Trie starts with the given prefix.longest_word()) - Finds and returns the longest word in the Trie.Why This is Needed
The Trie previously supported only basic operations like insertion, deletion, and searching. These new features significantly improve its usability by adding useful functionalities for searching, autocompletion, and prefix analysis.
How These Features Were Implemented
How to Test