We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
But this is far less memory efficient than implementing a trie. You're creating way too many strings. If you implemented a simple trie where each node had the letter it represented, an integer of all complete words its children makes, and a set of all its child nodes, the space would be significantly smaller and the lookup still linear.
EDIT: I take it back. Lookup in your solution is constant, not linear. So your solution is faster but uses more space.
The map you wrote has a space complexity of roughly O(kn), where k is the average number of letters in a word and n is the number of words. In a solution with a trie, the space complexity is O(n), where n is the total number of unique letters. More or less. I think in this case it's worth saving on space and sacrifice lookup.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Tries: Contacts
You are viewing a single comment's thread. Return to all comments →
But this is far less memory efficient than implementing a trie. You're creating way too many strings. If you implemented a simple trie where each node had the letter it represented, an integer of all complete words its children makes, and a set of all its child nodes, the space would be significantly smaller and the lookup still linear.
EDIT: I take it back. Lookup in your solution is constant, not linear. So your solution is faster but uses more space. The map you wrote has a space complexity of roughly O(kn), where k is the average number of letters in a word and n is the number of words. In a solution with a trie, the space complexity is O(n), where n is the total number of unique letters. More or less. I think in this case it's worth saving on space and sacrifice lookup.