4 ms·
Some come up with a greedy algorithm which finds the first prefix that is in the dictionary, and then returns whether the rest of the string is in the dictionar
by ttoinou 4y ago
Some come up with a greedy algorithm which finds the first prefix that is in the dictionary, and then returns whether the rest of the string is in the dictionary
I would do that straight away. I don't see the point of implementing the more complex and longer to code "double dictionary checking for all partitions of the string"
- behdad 4y agoConsider the string "thereis", and the dictionary {"there", "is"}. The greedy algorithm fails.
- behdad 4y agoMy bad. The dictionary should be {"the", "there", "is"}.
- whiddershins 4y agoI am now getting that I didn’t understand what you meant by greedy.
- ttoinou 4y agoOh yeah makes sense, if we don't do that the greedy way we could simply continue the search if it hasn't been found. That's what I would have done