0% completed
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
On this page