1178. Number of Valid Words for Each Puzzle LeetCode Solution

In this guide, you will get 1178. Number of Valid Words for Each Puzzle LeetCode Solution with the best time and space complexity. The solution to Number of Valid Words for Each Puzzle problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Number of Valid Words for Each Puzzle solution in C++
Number of Valid Words for Each Puzzle solution in Java
Number of Valid Words for Each Puzzle solution in Python
Additional Resources

1178. Number of Valid Words for Each Puzzle LeetCode Solution image

Problem Statement of Number of Valid Words for Each Puzzle

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].

Example 1:

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:

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

Constraints:

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

Complexity Analysis

Time Complexity:
Space Complexity:

1178. Number of Valid Words for Each Puzzle LeetCode Solution in C++

class Solution {
 public:
  vector<int> findNumOfValidWords(vector<string>& words,
                                  vector<string>& puzzles) {
    vector<int> ans;
    unordered_map<int, int> binaryCount;

    for (const string& word : words) {
      int mask = 0;
      for (char c : word)
        mask |= 1 << c - 'a';
      ++binaryCount[mask];
    }

    for (const string& puzzle : puzzles) {
      int valid = 0;
      const int n = puzzle.length() - 1;
      for (int i = 0; i < (1 << n); ++i) {
        int mask = 1 << puzzle[0] - 'a';
        for (int j = 0; j < n; ++j)
          if (i >> j & 1)
            mask |= 1 << puzzle[j + 1] - 'a';
        if (const auto it = binaryCount.find(mask); it != binaryCount.cend())
          valid += it->second;
      }
      ans.push_back(valid);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

1178. Number of Valid Words for Each Puzzle LeetCode Solution in Java

class Solution {
  public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
    List<Integer> ans = new ArrayList<>();
    Map<Integer, Integer> binaryCount = new HashMap<>();

    for (final String word : words) {
      int mask = 0;
      for (char c : word.toCharArray())
        mask |= 1 << (c - 'a');
      binaryCount.merge(mask, 1, Integer::sum);
    }

    for (final String puzzle : puzzles) {
      int valid = 0;
      final int n = puzzle.length() - 1;
      for (int i = 0; i < (1 << n); ++i) {
        int mask = 1 << puzzle.charAt(0) - 'a';
        for (int j = 0; j < n; ++j)
          if ((i >> j & 1) == 1)
            mask |= 1 << puzzle.charAt(j + 1) - 'a';
        if (binaryCount.containsKey(mask))
          valid += binaryCount.get(mask);
      }
      ans.add(valid);
    }

    return ans;
  }
}
// code provided by PROGIEZ

1178. Number of Valid Words for Each Puzzle LeetCode Solution in Python

class Solution:
  def findNumOfValidWords(
      self,
      words: list[str],
      puzzles: list[str],
  ) -> list[int]:
    ans = []
    binaryCount = collections.Counter()

    for word in words:
      mask = 0
      for c in word:
        mask |= 1 << string.ascii_lowercase.index(c)
      binaryCount[mask] += 1

    for puzzle in puzzles:
      valid = 0
      n = len(puzzle) - 1
      for i in range(1 << n):
        mask = 1 << ord(puzzle[0]) - ord('a')
        for j in range(n):
          if i >> j & 1:
            mask |= 1 << ord(puzzle[j + 1]) - ord('a')
        if mask in binaryCount:
          valid += binaryCount[mask]
      ans.append(valid)

    return ans
 # code by PROGIEZ