CODEWITHSUNDEEP
data-structurestrie
Coffee Maker
Coffee Maker

Reputation: 1573

Should searching for a substring of a key in a trie return true?

Say I have an empty trie T, and then I do T.insert("hello"). If I perform T.find("hell") then is that supposed to return true or false?

Upvotes: 0

Views: 40

Answers (2)

Steve Cooper
Steve Cooper

Reputation: 21480

Normally, when you store a word, you terminate with a node using a character like '*'.

Then implement a partial match method which returns true if your trie contains an appropriate path.

Then implement a full match method which is defined like

full_match(x): return partial_match(x + "*")

Upvotes: 0

konkked
konkked

Reputation: 3231

It should return all the partial matches, so in the case you're talking about should return {"hello"}, if it doesn't have a match would normally expect it to be an empty set being returned or null

Upvotes: 1

Related Questions