Word Search II

Trie
Hard

Approach

Diagrams

Analysis

Time

Space

from collections import defaultdict


class Solution:
    def findWords(self, board, words):
        self.wordsFoundOnBoard = []

        self.trie = Trie()

        self.board = board
        self.numRows = len(board)
        self.numCols = len(board[0])

        self.visited = [[False for col in range(self.numCols)] for row in range(self.numRows)]
        self.path = [self.trie.root]

        for word in words:
            self.trie.insert(word)

        for row in range(self.numRows):
            for col in range(self.numCols):
                if self.isCandidate(row, col):
                    self.dfs(row, col)

        return self.wordsFoundOnBoard

    def dfs(self, row, col):
        self.visited[row][col] = True

        curLetter = self.board[row][col]

        letterBeforeAsNode = self.path[-1]
        curLetterAsNode = letterBeforeAsNode.children[curLetter]

        if curLetterAsNode:
            self.path.append(curLetterAsNode)

        wordIsFound = curLetterAsNode.tail > 0

        if wordIsFound:
            word = self.getWord()
            self.wordsFoundOnBoard.append(word)
            curLetterAsNode.tail -= 1
            self.trie.remove(word)

        neighbors = self.getNeighbors(row, col)

        for nextRow, nextCol in neighbors:
            if self.isCandidate(nextRow, nextCol):
                self.dfs(nextRow, nextCol)

        self.path.pop()
        self.visited[row][col] = False

    def isCandidate(self, row, col):
        isOnBoard = 0 <= row < self.numRows and 0 <= col < self.numCols

        letter = self.board[row][col] if isOnBoard else '*'
        isVisited = self.visited[row][col] if isOnBoard else False
        isInTrie = letter in self.path[-1].children

        return isOnBoard and not isVisited and isInTrie

    def getWord(self):
        nodeVals = [node.val for node in self.path if node.val]
        word = ''.join(nodeVals)
        return word

    def getNeighbors(self, row, col):
        neighbors = []

        rowDeltas = [-1, 0, 1, 0]
        colDeltas = [0, 1, 0, -1]

        for delta in range(len(rowDeltas)):
            nextRow = row + rowDeltas[delta]
            nextCol = col + colDeltas[delta]
            neighbors.append((nextRow, nextCol))

        return neighbors


class TrieNode:
    def __init__(self, val=None):
        self.val = val
        self.children = defaultdict(TrieNode)
        self.tail = 0


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

    def insert(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 remove(self, word):
        path = [self.root]

        for letter in word:
            path.append(path[-1].children[letter])

        lastLetterInWordToRemove = path[-1]
        lastLetterInWordToRemove.tail = 0

        for letter in reversed(word):
            isNotLastLetterInWord = path[-1].tail == 0
            isNotUsedInOtherWord = len(path[-1].children) == 0

            if isNotLastLetterInWord and isNotUsedInOtherWord:
                path.pop()
                letterBefore = path[-1]
                del letterBefore.children[letter]

            else:
                break

Learn

#Backtracking

#Trie

Videos