Words That Fit Each Puzzle

Hard

In a word game, each puzzle is a string of letters, and its first letter is the *key letter*. A word fits a puzzle when: - the word contains the puzzle's key letter; - every letter of the word appears in the puzzle (letters in the word may repeat). Given a list of words words and a list of puzzles puzzles, return a list whose entry i is the number of words in words that fit puzzles[i]. There are many words and many puzzles, so checking every pair is too slow.

Example 1

words=["tool", "lot", "loot", "stool", "too"], puzzles=["tlo", "otsl", "lot"] → [4, 5, 3]

For "tlo": tool, lot, loot and too fit (stool has an s), so 4. For "otsl" all five words fit. For "lot" the key letter is l: too lacks it and stool has an s, leaving 3.

Example 2

words=["bee", "beef"], puzzles=["fbe", "zbe"] → [1, 0]

"fbe" requires an f, so only beef fits. The key letter of "zbe" is z, which no word contains, so 0.

Constraints

1 ≤ len(words) ≤ 10⁵
1 ≤ len(words[i]) ≤ 50
1 ≤ len(puzzles) ≤ 10⁴
1 ≤ len(puzzles[i]) ≤ 7
All strings consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Trie Array Hash Table String

Similar problems

Every Way to Space the Words Hard Glued Into a Palindrome Hard Best XOR Up the Chain of Command Hard Purge Twin Folders Hard Swapped Initials Names Hard

Input

words=["tool", "lot", "loot", "stool", "too"], puzzles=["tlo", "otsl", "lot"]

Expected

[4, 5, 3]

Run checks the first 3 tests in your browser. Submit checks all 35 tests on the server, hidden ones included.