LeetCode 212. Word Search II

Description

https://leetcode.com/problems/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"]

Note:

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

Explanation

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:
            trie.add(word)
            
        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:
            return
        
        if node.is_word:
            results.add(node.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:
                continue
            
            if (_x, _y) in visited:
                continue
                
            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 *