Leetcode Puzzle
Yesterday was the Lantern Festival, and leetcode’s daily question also came up with a question to guess the word puzzle.
Since I’m not good at real charades, let’s take a look at this algorithm’s charade.
First, the link to the topic:
https://leetcode-cn.com/problems/number-of-valid-words-for-each-puzzle/
Problem-solving ideas
We can design an algorithm to solve this puzzle problem.
First, we calculate the set Sw corresponding to each word and store it in a “data structure” for quick search in subsequent operations;
Then we enumerate each puzzle in turn, calculate its corresponding set Sp, and enumerate the subset S’p that meets the requirements. For each S’p, we look up the number of occurrences in the “data structure”, then the sum of the occurrences of all S’ps is the number of puzzles corresponding to the puzzle.
With this solution, we can think about how to design this data structure, so that we can quickly store and search.