[Leetcode]212. Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those 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"]

Although this is marked as a Hard question, it would not be that difficult to solve if you know trie and DFS.

The brute force approach is quite straightforward if you are familiar with backtracking/DFS. Simply we could explore the board starting with each cell and apply DFS. However, it would be extremely inefficient if, on each depth of searching, we check against each word in words again and again. For example, if we found that app does not exist, it’s safe to say that apple does not exist either. As you could notice, to optimize the brute force approach we need to find an efficient way of storing the strings in words. That’s where Trie comes to help.

Note: this post assumes you have the essential knowledge of backtracking and trie. Feel free to check the following posts to get started quickly with them if you want :P.

Logic

We can store the words in a trie and for each cell of the board, we apply DFS to search against the trie. Notably, we need to remove the word from words by setting is_word=False to avoid repeated computing and redundant results. Moreover, we can continuously pop matched leaves.

Code

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        # build a trie
        trie = {}
        for word in words:
            p = trie
            for char in word:
                p = p.setdefault(char, {})
            p['$'] = word
        row,col = len(board),len(board[0])
        ret = []
        # DFS
        def find(r0,c0,pp):
            char = board[r0][c0]
            p = pp[char]
            match = p.pop('$', False)
            if match:
                ret.append(match)
            board[r0][c0] = '#'
            for nr,nc in [(r0-1,c0),(r0+1,c0),(r0,c0-1),(r0,c0+1)]:
                if 0<=nr<row and 0<=nc<col and board[nr][nc] in p:
                    find(nr,nc,p)
            board[r0][c0] = char
            # remove matched leaves
            if not p:
                pp.pop(char)
        # search each cell in board
        for r in range(row):
            for c in range(col):
                if board[r][c] in trie:
                    find(r,c,trie)
                
        return ret
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments