0212-word-search-ii¶

Description¶

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⁴
1 <= words[i].length <= 10
words[i] consists of lowercase English letters.
All the strings of words are unique.

Solution(Python)¶

from collections import defaultdict

class TrieNode:
    def __init__(self):
        self.child = defaultdict(TrieNode)
        self.end = False
    
class Trie:
    def __init__(self):
        self.root = TrieNode() # root Node

    def insert(self, word):
        node = self.root
        for c in word:
            node = node.child[c]
        node.end = True

    def search(self, word):
        node = self.root
        for c in ord:
            node = node.children.get(c)
            if not node:
                return False
        return node.end

class Solution:
    # trie 
    #  store words in trie 
    # run dfs to find the words
    # Time Complexity: O(k*L+M*N*L)
    # Space COmplexity: O(K*L+M*N)
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        # construct  phase
        result = []
        trie = Trie()
        rootNode = trie.root

        for word in words:
            trie.insert(word)

        # search phase
        n = len(board)
        m = len(board[0])

        for i in range(n):
            for j in range(m):
                # run dfs
                self.dfs(board, rootNode, i, j, "", result)
        return result

    def dfs(self, board, node, i, j, path, result):
        if node.end:
            result.append(path)
            node.end = False
        # stopping condition
        # out of boundary 
        # node doesn't exist
        if i<0 or i>=len(board) or j < 0 or j >= len(board[0]):
            return
        currentCell = board[i][j] # using temparry cell to track by current cell value
        node  = node.child.get(currentCell)
        if not node:
            return
        board[i][j] = "#" # visited cell
        
        # adjacent check on four directions
        self.dfs(board, node, i+1, j, path+currentCell, result)
        self.dfs(board, node, i-1, j, path+currentCell, result)
        self.dfs(board, node, i, j+1, path+currentCell, result)
        self.dfs(board, node, i, j-1, path+currentCell, result)
        # restore cell value
        board[i][j] = currentCell




        