5 ms·
I don’t understand why the greedy solution is wrong. How can a word be the combination of two words if the first word isn’t a word? So, for example, if the fi
by whiddershins 4y ago
I don’t understand why the greedy solution is wrong.
How can a word be the combination of two words if the first word isn’t a word?
So, for example, if the first letter isn’t A or I, we can stop doing lookups for any combination of just a single letter and the remainder of the word.
Etc.
- behdad 4y agoImagine the string "there is", and the dictionary {"the", "there", "is"}.
- whiddershins 4y 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 4y 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 4y agoThat is a correct solution. The one I was talking about would stop after just trying "The" and "reis".
- whiddershins 4y agoOk
- roflyear 4y agoThis guy has a massive ego. Glad I do not work at Google.
- whiddershins 4y 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.
- the_af 4y agoIf I understand the example correctly, the problem with the incorrect greedy solution is that it locks on the first prefix it finds in the dictionary and then, if the rest of the string is not a word, fails. It's wrong because maybe the greedy prefix wasn't the right way to split.