[Leetcode] Problem 1178 - Number of Valid Words for Each Puzzle

Posted on | In ,

With respect to a given puzzle string, a word is valid if both the following conditions are satisfied:

  • word contains the first letter of puzzle.
  • For each letter in word, that letter is in puzzle.
    For example, if the puzzle is “abcdefg”, then valid words are “faced”, “cabbage”, and “baggage”; while invalid words are “beefed” (doesn’t include “a”) and “based” (includes “s” which isn’t in the puzzle).

Return an array answer, where answer[i] is the number of words in the given word list words that are valid with respect to the puzzle puzzles[i].

Example

Input:
words = [“aaaa”,”asas”,”able”,”ability”,”actt”,”actor”,”access”],
puzzles = [“aboveyz”,”abrodyz”,”abslute”,”absoryz”,”actresz”,”gaswxyz”]

Output: [1,1,3,2,4,0]

Explanation:
1 valid word for “aboveyz” : “aaaa”
1 valid word for “abrodyz” : “aaaa”
3 valid words for “abslute” : “aaaa”, “asas”, “able”
2 valid words for “absoryz” : “aaaa”, “asas”
4 valid words for “actresz” : “aaaa”, “asas”, “actt”, “access”
There’re no valid words for “gaswxyz” cause none of the words in the list contains letter ‘g’.

Constraints

  • 1 <= words.length <= 10^5
  • 4 <= words[i].length <= 50
  • 1 <= puzzles.length <= 10^4
  • puzzles[i].length == 7
  • words[i][j], puzzles[i][j] are English lowercase letters.
  • Each puzzles[i] doesn’t contain repeated characters.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
    List<Integer> result = new ArrayList<>();
    Map<Integer, Integer> frequency = new HashMap<>();

    for (String word : words) {
        int mask = 0;

        for (char ch : word.toCharArray())
            mask |= 1 << (ch - 'a');

        frequency.put(mask, frequency.getOrDefault(mask, 0) + 1);
    }

    for (String puzzle : puzzles) {
        int count = 0;
        int mask = 0;
        int first = puzzle.charAt(0) - 'a';

        for (char ch : puzzle.toCharArray())
            mask |= 1 << (ch - 'a');

        int subset = mask;

        while (subset > 0) {
            if (((subset >> first) & 1) == 1)
                count += frequency.getOrDefault(subset, 0);

            subset = (subset - 1) & mask;
        }

        result.add(count);
    }

    return result;
}