Count words obtained after adding a letter

Array Hash Table String Bit Manipulation Sorting

43.9% acceptance

Feb 25, 2026

723

169

You are given two 0-indexed arrays of strings startWords and targetWords. Each string consists of lowercase English letters only. For each string in targetWords, check if it is possible to choose a string from startWords and perform a conversion operation on it to be equal to that from targetWords. The conversion operation is described in the following two steps: Append any lowercase letter that is not present in the string to its end. Rearrange the letters of the new string in any arbitrary order. Return the number of strings in targetWords that can be obtained by performing the operations on any string of startWords. Note that you will only be verifying if the string in targetWords can be obtained from a string in startWords by performing the operations. The strings in startWords do not actually change during this process.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn word_count(start_words: Vec<String>, target_words: Vec<String>) -> i32 {
    use std::collections::HashSet;
    let start_masks: HashSet<u32> = start_words
      .iter()
      .map(|w| w.bytes().fold(0u32, |mask, b| mask | (1 << (b - b'a'))))
      .collect();

    target_words
      .iter()
      .filter(|t| {
        let mask = t.bytes().fold(0u32, |m, b| m | (1 << (b - b'a')));
        (0u32..26).any(|bit| {
          (mask >> bit) & 1 == 1 && start_masks.contains(&(mask ^ (1 << bit)))
        })
      })
      .count() as i32
  }
}