Number of Valid Words for Each Puzzle

Trie
Hard

Approach

Diagrams

Analysis

Time

Space

class Solution:
    def findNumOfValidWords(self, words, puzzles):
        answer = []

        words = [set(word) for word in words]
        puzzles = [(puzzle[0], set(puzzle)) for puzzle in puzzles]

        alphabet = [Trie() for letter in range(26)]

        for word in words:
            for letter in word:
                letterIdx = self.getLetterIdx(letter)
                trie = alphabet[letterIdx]
                trie.insertWord(word)

        for firstLetter, puzzle in puzzles:
            letterIdx = self.getLetterIdx(firstLetter)
            trie = alphabet[letterIdx]
            numOfValidWords = trie.findNumOfValidWords(puzzle)
            answer.append(numOfValidWords)

        return answer

    def getLetterIdx(self, letter):
        return ord(letter) - 97


class TrieNode():
    def __init__(self, val):
        self.val = val
        self.children = {}
        self.tail = 0


class Trie():
    def __init__(self):
        self.root = TrieNode(None)

    def insertWord(self, word):
        node = self.root

        for letter in word:
            if letter not in node.children:
                node.children[letter] = TrieNode(letter)

            node = node.children[letter]

        node.tail += 1

    def findNumOfValidWords(self, puzzle):
        def dfs(node):
            nonlocal numOfValidWords

            numOfValidWords += node.tail

            for child in node.children:
                if child in puzzle:
                    dfs(node.children[child])

        numOfValidWords = 0
        dfs(self.root)
        return numOfValidWords

Learn

#Trie

#Depth-First Search

Videos