3 ms·
I guess you're assuming a hash set and ignoring collisions? So you fill the set with in O(1*N), again loop through the (original?) list assuming its O(N) to do
by jayd16 6y ago
I guess you're assuming a hash set and ignoring collisions?
So you fill the set with in O(1*N), again loop through the (original?) list assuming its O(N) to do so searching the set for replacements?
So at least a few passes through every element.
You could actually reduce this by excluding elements as you insert. You don't need to fill your search space with with anything that has a "b" for example, eliminating inserts.
- raldi 6y agoOf course I'm ignoring collisions — it's a wordlist.
- jayd16 6y agoNo collisions in the input does not mean no collisions in the hash algorithm. In reality there's book keeping overhead in a hash data structure that might be significant.
- YeGoblynQueenne 6y ago>> You could actually reduce this by excluding elements as you insert. You don't need to fill your search space with with anything that has a "b" for example, eliminating inserts. I'm not sure that works. Suppose "abab" and "abao" are words. Note the problem spec says "after replacing a b with an o", i.e. after replacing _one_ b in a word with an o. If you exclude all words with a "b" and replace one b with an o in "abab" you will get "abao" which you have excluded, so you will think it's not a word. I think at best you can ignore only words with a single b.
- jayd16 6y agoOh true, I didn't consider wording closely enough. I think you might be right. However you can skip words that started with no Bs as clearly still being words without a search and you can remove search words with no Os.