212. Word Search II

Problem Statement

link: https://leetcode.com/problems/word-search-ii/ https://leetcode.cn/problems/word-search-ii/

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:

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: []

Solution Approach

The problem can be solved using a Trie data structure to efficiently search for words on the board. We traverse the board, and at each cell, we perform a depth-first search to find words that match the Trie structure.

Algorithm

1. Initialize a Trie data structure containing all the words from the ‘words’ list, marking the end of each word with a ‘#’ character.
2. Iterate through each cell on the board and perform a depth-first search (DFS) to find valid words. When a valid word is found, add it to the result list.
3. Explore adjacent cells in the DFS, marking visited cells and backtracking when necessary, and return the list of found words.

Implement

    class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        def dfs(x, y, root):
            l = board[x][y]
            cur = root[l]
            word = cur.pop('#',False)
            if word:
                res.append(word)
            board[x][y] = '*'
            for dirx, diry in [(0, 1),(0, -1),(1, 0),(-1, 0)]:
                curx, cury = x + dirx, y + diry
                if 0 <= curx < m and 0 <= cury < n and board[curx][cury] in cur:
                    dfs(curx, cury, cur)
            board[x][y] = l
            if not cur:
                root.pop(l)

        trie = {}
        for word in words:
            cur = trie
            for l in word:
                cur = cur.setdefault(l, {})
            cur['#'] = word
        m, n = len(board), len(board[0])
        res = []
        for i in range(m):
            for j in range(n):
                if board[i][j] in trie:
                    dfs(i, j, trie)
        return res
 

    
    

Twitter  facebook  Email