3 ms·
There are a finite number of words in the dictionary, which implies there is an upper bound in the length of words. The maximum number of iterations is the len
by abtinf 4y ago
There are a finite number of words in the dictionary, which implies there is an upper bound in the length of words.
The maximum number of iterations is the length of the longest word in the dictionary.
This means that part 1 of the problem can be solved in O(1)+O(1).
That doesn’t mean you will be happy with it. Not all O(1)s are equal.
- hhmc 4y agoSimilarly you can precompute a dictionary for the Cartesian product of the dictionary with itself, then lookup into that. Big in space but O(1) (wrt word len at least)
- abtinf 4y agoExcellent point. The only way to evaluate if this is a good or bad solution is the actual operational context. If you had a service that had to do millions of these matches per second with low latency, then this might be a reasonable solution.