Algorithm

Problem Name: 1178. Number of Valid Words for Each Puzzle

Problem Link: https://leetcode.com/problems/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.

Code Examples

#1 Code Example with Javascript Programming

Code - Javascript Programming


const findNumOfValidWords = function(words, puzzles) {
  let n = puzzles.length,
    offset = 'a'.charCodeAt()
  let res = new Array(n).fill(0)
  let cnt = {}

  for (let w of words) {
    let mask = 0
    for (let c of w) {
      mask |= 1 << (c.charCodeAt() - offset)
    }
    cnt[mask] = ~~cnt[mask] + 1
  }
  for (let i = 0; i  <  n; i++) {
    let s = puzzles[i],
      len = s.length
    for (let k = 0; k  <  1 << (len - 1); k++) {
      let mask = 1 << (s[0].charCodeAt() - offset)
      for (let j = 0; j  <  len - 1; j++) {
        if (k & (1 << j)) {
          mask |= 1 << (s[j + 1].charCodeAt() - offset)
        }
      }
      res[i] += ~~cnt[mask]
    }
  }
  return res
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
words = ["aaaa","asas","able","ability","actt","actor","access"], puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]

Output

x
–
+
cmd
[1,1,3,2,4,0]

#2 Code Example with Python Programming

Code - Python Programming


from itertools import combinations as cb
class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        cnt = collections.Counter(''.join(sorted(set(w))) for w in words)
        return [sum(cnt[''.join(sorted(s + (p[0], )))] for l in range(len(p)) for s in cb(p[1:], l)) for p in puzzles]
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
words = ["aaaa","asas","able","ability","actt","actor","access"], puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]

Output

x
–
+
cmd
[1,1,3,2,4,0]
Advertisements

Demonstration

Previous
#1177 Leetcode Can Make Palindrome from Substring Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#1179 Leetcode Reformat Department Table Solution in SQL Leetcode