212.Word_Search_II(Hard).md

212. Word Search II (Hard)

Date and Time: Aug 14, 2024, 22:20 (EST)

Link: https://leetcode.com/problems/word-search-ii/

Question:

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example 1:

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"]

Example 2:

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

Output: []

Constraints:

• m == board.length

• n == board[i].length

• 1 <= m, n <= 12

• board[i][j] is a lowercase English letter.

• 1 <= words.length <= 3 * 10^4

• 1 <= words[i].length <= 10

• words[i] consists of lowercase English letters.

• All the strings of words are unique.

Walk-through:

1. Similar to previous questions, we need to create TrieNode() to store each word into Trie. We can define an extra variable self.count to count for how many times a node is used, so we can stop backtracking early. TrieNode() class with add() and remove() method.

2. We run dfs on all grid on board to try all combinations from the board[r][c] we start, if a word exists, we add it to res and set curr.endOfWord = False and remove word from root to stop backtracking early.

Python Solution:

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

    def add(self, word):
        curr = self
        curr.count += 1
        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
            curr.count += 1
        curr.endOfWord = True

    def remove(self, word):
        curr = self
        curr.count -= 1
        for c in word:
            if c in curr.children:
                curr = curr.children[c]
                curr.count -= 1

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        res, visited = set(), set()
        rows, cols = len(board), len(board[0])
        root = TrieNode()
        for word in words:
            root.add(word)

        def dfs(r, c, node, word):
            if r not in range(rows) or c not in range(cols) or (r, c) in visited or board[r][c] not in node.children or node.children[board[r][c]].count < 1:
                return
            visited.add((r, c))
            node = node.children[board[r][c]]
            word += board[r][c]
            if node.endOfWord:
                node.endOfWord = False
                res.add(word)
                root.remove(word)
            dfs(r+1, c, node, word)
            dfs(r-1, c, node, word)
            dfs(r, c+1, node, word)
            dfs(r, c-1, node, word)
            visited.remove((r, c))

        for r in range(rows):
            for c in range(cols):
                dfs(r, c, root, "")
        
        return list(res)

Time Complexity: $O((m * n) * 4^{m n})$, each dfs search on 4 directions of all the board, and we need to run dfs on all grids, which is $m * n$ area.
Space Complexity: $O(\text{len(all characters of all words)})$