Using bit manipulation to speed up the computation

Solution 1: brute force by organizing the words in 26 categories (run time 1016 ms).

  • Naively change words into integers by using bit minupulation.
  • Organize the words in 26 categories. (has “a”, has “b”, …)
  • For each puzzle, check the words in the category of puzzle[0]

The complexity for this one is hard to analysis. I though it may get TLE, actually, it can get AC. The reason should be C++ and bit manipulation are fast.

Solution 2: Check each subset of a puzzle (108 ms).

The idea is checking each subset of a puzzle

As each puzzle has length of 7 and we have to include the first one, so we only have 2⁶ possibilities. The complexity will be O(M*2⁶) where M is the length of the puzzles.

Python code will be much shorter by using frozen set. The reason of using frozen set is it is hashable.

Thanks for reading.