Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Flaw/Issue with StartsWith solution

jmezzbmxer

Dec 7, 2024

Should startsWith not be checking to ensure there are children present, rather than simply excluding an isEnd check when comparing it to the search function?

This may be an issue of semantics, but if you had a test case which consists of the following;

['Trie', 'insert('app')', 'startsWith('app')']

Does the word "app" really have a prefix of app? I would think a prefix can not be a word on it's own, so despite us not checking if it's the end of a word the provided solution is not checking if it's actually a prefix of a word. The current solution would return True to that startsWith call.

Adding an additional check like the following would be ensuring this is an actual prefix rather than a full word. This would only be adding O(1) to the time complexity (essentially a loop with a maximum of 26 runs, worst case checking a z child).

if len(node.children) > 0: return True

The full method should (in my eyes) look something like this;

def startsWith(self, prefix: str) -> bool: node = self.root for char in prefix: if char not in node.children: return False node = node.children[char] if len(node.children) > 0: return True return False

0

0

Comments
Comments

On this page