Problem

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" (does not include 'a') and "based" (includes 's' which is not in the puzzle).

Return an arrayanswer , whereanswer[i]is the number of words in the given word listwords that is valid with respect to the puzzlepuzzles[i].

Examples

Example 1

1
2
3
4
5
6
7
8
9

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 are no valid words for "gaswxyz" cause none of the words in the list contains letter 'g'.

Example 2

1
2

Input: words = ["apple","pleas","please"], puzzles = ["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"]
Output: [0,1,3,2,0]

Constraints

  • 1 <= words.length <= 10^5
  • 4 <= words[i].length <= 50
  • 1 <= puzzles.length <= 10^4
  • puzzles[i].length == 7
  • words[i] and puzzles[i] consist of lowercase English letters.
  • Each puzzles[i] does not contain repeated characters.

Solution

Method 1 – Bitmasking and Hash Map

Intuition

Each word and puzzle can be represented as a bitmask. For each puzzle, enumerate all its subsets that include the first letter, and count how many words have the same bitmask.

Approach

  1. For each word, compute its bitmask and count the frequency in a hash map.
  2. For each puzzle, enumerate all subsets of its letters that include the first letter (using bitmask subset enumeration).
  3. For each subset, add the count from the hash map to the answer for that puzzle.
  4. Return the answer array.

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

class Solution {
public:
    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
        unordered_map<int, int> freq;
        for (auto& w : words) {
            int mask = 0;
            for (char c : w) mask |= 1 << (c - 'a');
            freq[mask]++;
        }
        vector<int> ans;
        for (auto& p : puzzles) {
            int mask = 0;
            for (char c : p) mask |= 1 << (c - 'a');
            int first = 1 << (p[0] - 'a');
            int sub = mask, cnt = 0;
            do {
                if (sub & first) cnt += freq[sub];
                sub = (sub - 1) & mask;
            } while (sub != mask);
            ans.push_back(cnt);
        }
        return ans;
    }
};
 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

func findNumOfValidWords(words []string, puzzles []string) []int {
    freq := map[int]int{}
    for _, w := range words {
        mask := 0
        for _, c := range w {
            mask |= 1 << (c - 'a')
        }
        freq[mask]++
    }
    ans := make([]int, len(puzzles))
    for i, p := range puzzles {
        mask := 0
        for _, c := range p {
            mask |= 1 << (c - 'a')
        }
        first := 1 << (p[0] - 'a')
        sub := mask
        cnt := 0
        for {
            if sub&first != 0 {
                cnt += freq[sub]
            }
            if sub == 0 { break }
            sub = (sub - 1) & mask
        }
        ans[i] = cnt
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (String w : words) {
            int mask = 0;
            for (char c : w.toCharArray()) mask |= 1 << (c - 'a');
            freq.put(mask, freq.getOrDefault(mask, 0) + 1);
        }
        List<Integer> ans = new ArrayList<>();
        for (String p : puzzles) {
            int mask = 0;
            for (char c : p.toCharArray()) mask |= 1 << (c - 'a');
            int first = 1 << (p.charAt(0) - 'a');
            int sub = mask, cnt = 0;
            do {
                if ((sub & first) != 0) cnt += freq.getOrDefault(sub, 0);
                sub = (sub - 1) & mask;
            } while (sub != mask);
            ans.add(cnt);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    fun findNumOfValidWords(words: Array<String>, puzzles: Array<String>): List<Int> {
        val freq = mutableMapOf<Int, Int>()
        for (w in words) {
            var mask = 0
            for (c in w) mask = mask or (1 shl (c - 'a'))
            freq[mask] = freq.getOrDefault(mask, 0) + 1
        }
        val ans = mutableListOf<Int>()
        for (p in puzzles) {
            var mask = 0
            for (c in p) mask = mask or (1 shl (c - 'a'))
            val first = 1 shl (p[0] - 'a')
            var sub = mask; var cnt = 0
            do {
                if ((sub and first) != 0) cnt += freq.getOrDefault(sub, 0)
                sub = (sub - 1) and mask
            } while (sub != mask)
            ans.add(cnt)
        }
        return ans
    }
}
 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

class Solution:
    def findNumOfValidWords(self, words: list[str], puzzles: list[str]) -> list[int]:
        from collections import Counter
        freq = Counter()
        for w in words:
            mask = 0
            for c in set(w):
                mask |= 1 << (ord(c)-97)
            freq[mask] += 1
        ans = []
        for p in puzzles:
            mask = 0
            for c in p:
                mask |= 1 << (ord(c)-97)
            first = 1 << (ord(p[0])-97)
            sub = mask
            cnt = 0
            while True:
                if sub & first:
                    cnt += freq[sub]
                if sub == 0:
                    break
                sub = (sub-1) & mask
            ans.append(cnt)
        return ans
 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

use std::collections::HashMap;
impl Solution {
    pub fn find_num_of_valid_words(words: Vec<String>, puzzles: Vec<String>) -> Vec<i32> {
        let mut freq = HashMap::new();
        for w in words.iter() {
            let mut mask = 0;
            for c in w.chars() { mask |= 1 << (c as u8 - b'a'); }
            *freq.entry(mask).or_insert(0) += 1;
        }
        let mut ans = Vec::with_capacity(puzzles.len());
        for p in puzzles.iter() {
            let mut mask = 0;
            for c in p.chars() { mask |= 1 << (c as u8 - b'a'); }
            let first = 1 << (p.chars().next().unwrap() as u8 - b'a');
            let mut sub = mask;
            let mut cnt = 0;
            loop {
                if sub & first != 0 { cnt += *freq.get(&sub).unwrap_or(&0); }
                if sub == 0 { break; }
                sub = (sub-1) & mask;
            }
            ans.push(cnt);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    findNumOfValidWords(words: string[], puzzles: string[]): number[] {
        const freq = new Map<number, number>()
        for (const w of words) {
            let mask = 0
            for (const c of new Set(w)) mask |= 1 << (c.charCodeAt(0) - 97)
            freq.set(mask, (freq.get(mask) || 0) + 1)
        }
        const ans: number[] = []
        for (const p of puzzles) {
            let mask = 0
            for (const c of p) mask |= 1 << (c.charCodeAt(0) - 97)
            const first = 1 << (p.charCodeAt(0) - 97)
            let sub = mask, cnt = 0
            do {
                if (sub & first) cnt += freq.get(sub) || 0
                sub = (sub - 1) & mask
            } while (sub !== mask)
            ans.push(cnt)
        }
        return ans
    }
}

Complexity

  • ⏰ Time complexity: O(N + Q * 2^7), where N is the number of words and Q is the number of puzzles.
  • 🧺 Space complexity: O(N), for the frequency map.