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.


board = [
words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]


  1. All inputs are consist of lowercase letters a-z.
  2. The values of words are distinct.


use trie + backtracking

Python Solution

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False
        self.word = None
class Trie:
    def __init__(self):
        self.root = TrieNode()
    def add(self, word):
        node = self.root
        for char in word:        
            child = node.children.get(char)
            if not child:
                child = TrieNode()
                node.children[char] = child
            node = child
        node.is_word = True
        node.word = word
    def find(self, word):
        node = self.root
        for char in word:
            child = node.children.get(char)
            if not child:
                return None
            node = child
        return node        
class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        if not board:
            return []
        trie = Trie()
        for word in words:
        results = set()

        for i in range(0, len(board)):
            for j in range(0, len(board[0])):    
                char = board[i][j]                
                self.search_helper(results, board, i, j, trie.root.children.get(char), set([(i, j)]))
        return list(results)
    def search_helper(self, results, board, x, y, node, visited):
        if node is None:
        if node.is_word:
        directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
        for delta_x, delta_y in directions:
            _x = x + delta_x
            _y = y + delta_y
            if _x < 0 or _x > len(board) - 1 or _y < 0 or _y > len(board[0]) - 1:
            if (_x, _y) in visited:
            visited.add((_x, _y))
            self.search_helper(results, board, _x, _y, node.children.get(board[_x][_y]), visited)
            visited.remove((_x, _y))
  • Time Complexity: ~M(4 *3^ (L – 1))
  • Space Complexity: ~N

where M is the number of cells in the board and L is the maximum length of words.

where N is the total number of letters in the dictionary.

Leave a Reply

Your email address will not be published. Required fields are marked *