LeetCode 212. Word Search II

Description

https://leetcode.com/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 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 * 104
• 1 <= words[i].length <= 10
• words[i] consists of lowercase English letters.
• All the strings of words are unique.

Explanation

Similar to Word Search, we can use the backtracking algorithm to solve the problem. Backtracking is a methodology where we mark the current path of exploration, if the path does not lead to a solution, we then revert the change (i.e. backtracking) and try another path.

The difference is that for this problem, for each word we would conduct a backtracking search.

As the general idea for each word search, we would walk around the 2D board, at each step we compare the board character with the first remaining character of the word. If matched, we continued on the path. If not, we give up the path. And at each step, we would mark or revert our visit so that we won’t have duplicated visits. Finally, if no more character left for the word, we find the word.

Python Solution I

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        results = []
        
        for word in words:
            is_found = False
            
            for i in range(len(board)):
                if is_found:
                    break                
                for j in range(len(board[0])):
                    if is_found:
                        break
                    
                    if self.search_helper(board, i, j, word):
                        results.append(word)
                        is_found = True

        return results
    
    def search_helper(self, board, i, j, word):
        if not word:
            return True
        
        if i < 0 or i > len(board) - 1 or j < 0 or j > len(board[0]) - 1:
            return False

        if board[i][j] != word[0]:
            return False
        
        char = board[i][j]
        board[i][j] = '#'
        
        left = self.search_helper(board, i - 1, j, word[1:])
        right = self.search_helper(board, i + 1, j, word[1:])
        up = self.search_helper(board, i, j + 1, word[1:])
        down = self.search_helper(board, i, j - 1, word[1:])
        
        board[i][j] = char        
        
        return left or right or up or down

• Time Complexity: O(M *N * 4^L), where M is the number of words.
• Space Complexity: O(M *N * 4^L), where M is the number of words.

Python Solution II

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.