3 ms·

I actually have had to solve a version of this problem on the job. There was a database of tagged photos; for some reason all the tag strings had had their spac

I actually have had to solve a version of this problem on the job. There was a database of tagged photos; for some reason all the tag strings had had their spaces stripped. So you had to efficiently find a probable chunking into words. (Of course the original text wasn't always all dictionary words.) OTOH re the concern for O(n^2) time when n is bounded by word lengths, and when the inner loop was in already-optimized string comparisons in your language's hashtable library -- I think that part is very artificial.

dmurray 4y ago
> OTOH re the concern for O(n^2) time when n is bounded by word lengths, and when the inner loop was in already-optimized string comparisons in your language's hashtable library -- I think that part is very artificial. Yes! The candidate already optimized for the important thing (which the author forgot about and added in a footnote), which is that the list of words could be very long, and that the words in an English dictionary are relatively short. Optimising for the important factors based on an assessment of the problem domain is actually a more important skill than regurgitating the best algorithm from the book. If the author wanted to suggest a solution suitable for very long needles, he should have used a different domain like, say, gene sequencing.