Number of valid words for each puzzle

Array Hash Table String Bit Manipulation Trie

47.7% acceptance

Feb 25, 2026

1301

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 array answer, where answer[i] is the number of words in the given word list words that is valid with respect to the puzzle puzzles[i].

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;
impl Solution {
  pub fn find_num_of_valid_words(words: Vec<String>, puzzles: Vec<String>) -> Vec<i32> {
    // For each word, compute its bitmask (which letters it contains)
    let mut word_mask_count: HashMap<u32, i32> = HashMap::new();
    for w in &words {
      let mask = w.bytes().fold(0u32, |acc, c| acc | (1 << (c - b'a')));
      *word_mask_count.entry(mask).or_insert(0) += 1;
    }
    puzzles.iter().map(|p| {
      let p_bytes = p.as_bytes();
      let first_bit = 1u32 << (p_bytes[0] - b'a');
      let p_mask = p_bytes.iter().fold(0u32, |acc, &c| acc | (1 << (c - b'a')));
      // Enumerate all subsets of p_mask that contain first_bit
      let mut count = 0i32;
      let mut sub = p_mask;
      loop {
        if sub & first_bit != 0 {
          count += word_mask_count.get(&sub).copied().unwrap_or(0);
        }
        if sub == 0 { break; }
        sub = (sub - 1) & p_mask;
      }
      count
    }).collect()
  }
}