We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Word Search II

Difficulty: Hard

Problem Description

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.

Key Insights

  • The problem involves searching for words in a grid of characters.
  • Words can be formed by moving horizontally or vertically in the grid.
  • Efficient searching can be achieved using a Trie data structure to store the list of words.
  • Backtracking is a suitable algorithmic approach to explore possible paths in the grid.

Space and Time Complexity

Time Complexity: O(m * n * 4^L + W), where m and n are the dimensions of the board, L is the maximum length of the words, and W is the number of words.
Space Complexity: O(W + L), where W is the number of words and L is the maximum length of the words stored in the Trie.

Solution

To solve the problem, we will use a Trie to store all the words we need to search for. The Trie allows us to efficiently check if a prefix of a word exists in our list of words while we traverse the board. We will then use backtracking to explore all possible paths on the board starting from each cell. During the exploration, we will mark cells as visited to avoid using them more than once in a word.

  1. Build a Trie from the list of words.
  2. Iterate through each cell in the board and start backtracking.
  3. For each cell, check if it can lead to a valid prefix in the Trie.
  4. If a complete word is found, add it to the results.
  5. Continue exploring until all possibilities have been checked.

Code Solutions

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

def find_words(board, words):
    trie = Trie()
    for word in words:
        trie.insert(word)
    
    result = set()
    m, n = len(board), len(board[0])
    
    def backtrack(x, y, node, path):
        char = board[x][y]
        node = node.children.get(char)
        if not node:
            return
        
        if node.is_end_of_word:
            result.add(path + char)
            node.is_end_of_word = False  # Avoid duplicates
        
        board[x][y] = '#'  # Mark as visited
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            new_x, new_y = x + dx, y + dy
            if 0 <= new_x < m and 0 <= new_y < n and board[new_x][new_y] != '#':
                backtrack(new_x, new_y, node, path + char)
        board[x][y] = char  # Unmark for backtracking
    
    for i in range(m):
        for j in range(n):
            backtrack(i, j, trie.root, "")
    
    return list(result)
← Back to All Questions