Leetcode 212. Word Search II

Problem

Leetcode 212 - Word Search II

Example:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

Approach

Using backtracking/DFS and TrieNode, we can solve the question.

Here is the Python code for the solution:

class TrieNode:
    def __init__(self):
        self.letterMap = {}
        self.endOfWord = False

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = TrieNode()
        
        for w in words:
            curr = root
            for ch in w:
                if not ch in curr.letterMap:
                    curr.letterMap[ch] = TrieNode()
                curr = curr.letterMap[ch]
            curr.endOfWord = True
        
        visited = [[False for _ in range(len(board[0]))] for _ in range(len(board))]
        res = set()

        def dfs(i, j, curr, w):
            if (i < 0 or j < 0 or i >= len(board) or j >= len(board[0]) or 
                visited[i][j] or board[i][j] not in curr.letterMap):
                return

            visited[i][j] = True
            curr = curr.letterMap[board[i][j]]
            w += board[i][j]
            if curr.endOfWord:
                res.add(w)
            
            dfs(i+1, j, curr, w)
            dfs(i-1, j, curr, w)
            dfs(i, j+1, curr, w)
            dfs(i, j-1, curr, w)
            visited[i][j] = False
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                dfs(i, j, root, '')
        
        return list(res)

Time Complexity and Space Complexity

Time Complexity: $O(mn4*3^(t-1)+s)$ where $m$ is number of rows $n$ is number of columns, $t$ is the max length of any word in the array, $s$ is the sum of the lengths of all words

Space Complexity: $O(s)$