4 ms·
Imagine the string "there is", and the dictionary {"the", "there", "is"}.
by behdad 3y ago
Imagine the string "there is", and the dictionary {"the", "there", "is"}.
- whiddershins 3y agoT isn’t a word, next Th isn’t a word, next The is a word, look up ‘reis’, not a word, next Ther isn’t a word, next There is a word, look up ‘is’ it is a word, return true If you don’t want to ignore whitespace, than I’m not sure what behavior you want, you want “there is” to return false? If whitespace is the delimiter the whole thing is trivial, you split on space. I am now more confused.
- the_af 3y ago> The is a word, look up ‘reis’, not a word, next This is where the wrong greedy solution from TFA, which the author claims some candidates reach, stops. So it's wrong. Note that if you do not stop, and continue as in your own example, your solution isn't "greedy"!
- behdad 3y agoThat is a correct solution. The one I was talking about would stop after just trying "The" and "reis".
- whiddershins 3y agoOk
- roflyear 3y agoThis guy has a massive ego. Glad I do not work at Google.
- whiddershins 3y agoAnyway, don’t you get a savings by using some data structure that indexes the dictionary by word length first? Or at least sorting by.