3 ms·

Set lookup is O(1), and with this data structure is synonymous with get and exists. Insert is O(1). Remove is irrelevant.

• 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 ago
    Of course I'm ignoring collisions — it's a wordlist.
    • jayd16 6y ago
      No 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 ago
      Oh 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.