Interview Prepsubsets-combinationshardAmazonGoogleFacebook

Number of Valid Words for Each Puzzle

Choose your preparation mode4 modes available

Try It Solution Trace

Start learning this pattern below

Jump into concepts and practice - no test required

Recommended

Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong

▶

Steps

setup

Initialize Trie and Insert Word Masks

Start by creating an empty trie root node. Prepare to insert bitmask representations of words with up to 7 unique letters.

💡 Building the trie is essential to efficiently represent all word letter subsets for quick lookup during puzzle queries.

Line:self.root = TrieNode()

💡 The trie root node is the starting point for all word insertions and puzzle traversals.

from typing import List

class TrieNode:
    def __init__(self):
        self.count = 0
        self.children = {}

class Solution:
    def __init__(self):
        self.root = TrieNode()  # STEP 1

    def insert(self, mask):
        node = self.root
        for i in range(26):  # STEP 2-4
            bit = (mask >> i) & 1
            if bit:
                if i not in node.children:
                    node.children[i] = TrieNode()
                node = node.children[i]
        node.count += 1

    def dfs(self, node, puzzle_mask, first_bit, has_first):
        res = node.count if has_first else 0  # STEP 7,12,19
        for i, child in node.children.items():
            if (puzzle_mask & (1 << i)) != 0:  # STEP 6,9,15,16,17,18
                res += self.dfs(child, puzzle_mask, first_bit, has_first or (i == first_bit))
        return res  # STEP 13,20

    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        for word in words:  # STEP 2-4
            mask = 0
            for ch in set(word):
                mask |= 1 << (ord(ch) - ord('a'))
            if bin(mask).count('1') <= 7:
                self.insert(mask)

        res = []
        for puzzle in puzzles:  # STEP 5,14
            first_bit = ord(puzzle[0]) - ord('a')
            puzzle_mask = 0
            for ch in puzzle:
                puzzle_mask |= 1 << (ord(ch) - ord('a'))
            res.append(self.dfs(self.root, puzzle_mask, first_bit, False))
        return res

if __name__ == "__main__":
    words = ["aaaa","asas","able","ability","actt","actor","access"]
    puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
    sol = Solution()
    print(sol.findNumOfValidWords(words, puzzles))  # STEP 20

📊

Number of Valid Words for Each Puzzle - Watch the Algorithm Execute, Step by Step

Watching the trie construction and recursive traversal step-by-step reveals how bitmasking and pruning efficiently solve a complex subset problem.

Step 1/20

·Active fill★Answer cell

entering

Call Path (current → root)

root call

Practice

(1/5)

1. Consider the following Python code implementing combination sum with reuse allowed:

from typing import List

def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
    candidates.sort()
    result = []
    def backtrack(index, path, target):
        if target == 0:
            result.append(path[:])
            return
        if index == len(candidates) or target < 0:
            return
        max_use = target // candidates[index]
        for count in range(max_use + 1):
            backtrack(index + 1, path + [candidates[index]] * count, target - candidates[index] * count)
    backtrack(0, [], target)
    return result

print(combinationSum([2,3,6,7], 7))

What is the exact output of this code?

easy

A. [[7]]

B. [[2, 2, 3], [7]]

C. [[2, 2, 3]]

D. [[7], [2, 2, 3]]

4. The following code attempts to count subsets with sum K using space-optimized DP. Identify the line that contains a subtle bug that can cause incorrect results.

def count_subsets_space_optimized(arr, K):
    dp = [0] * (K + 1)
    dp[0] = 1
    for num in arr:
        for j in range(num, K + 1):
            dp[j] += dp[j - num]
    return dp[K]

medium

A. for j in range(num, K + 1):

B. dp[0] = 1

C. dp = [0] * (K + 1)

D. dp[j] += dp[j - num]

Start learning this pattern below

Initialize Trie and Insert Word Masks

Insert mask for word 'aaaa' into trie

Insert mask for word 'asas' into trie

Insert mask for word 'able' into trie

Start DFS for puzzle 'aboveyz'

DFS explores child node for letter 'a' (bit 0)

DFS counts words ending at node for 'a'

DFS explores child node for letter 's' (bit 18) from 'a'

DFS explores child node for letter 'b' (bit 1) from 'a'

DFS explores child node for letter 'e' (bit 4) from 'b'

DFS explores child node for letter 'l' (bit 11) from 'e'

Count words ending at node for 'l'

Backtrack and finish DFS for puzzle 'aboveyz'

Start DFS for puzzle 'abslute'

DFS explores child node for letter 'a' (bit 0) for 'abslute'

DFS explores child node for letter 'b' (bit 1) from 'a' for 'abslute'

DFS explores child node for letter 'e' (bit 4) from 'b' for 'abslute'

DFS explores child node for letter 'l' (bit 11) from 'e' for 'abslute'

Count words ending at node for 'l' for 'abslute'

Final aggregation and output

Key Takeaways

Practice

Solution

Step 1: Trace backtrack calls for candidates=[2,3,6,7], target=7

Step 2: Check order of results appended

Final Answer:

Quick Check:

Solution

Step 1: Understand problem constraints

Step 2: Identify suitable algorithm

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem

Step 2: Identify the approach that enumerates all subsets

Final Answer:

Quick Check:

Solution

Step 1: Analyze iteration order

Step 2: Correct iteration direction

Final Answer:

Quick Check:

Solution

Step 1: Identify outer loop complexity

Step 2: Identify inner loop complexity

Final Answer:

Quick Check: