Word Search II


Problem clarification

The problem requires us to find all the words from a given list in a 2D board of characters. We can only move horizontally or vertically in the board to form words. We need to return a list of all the words found.

Problem analysis

  • Input: A 2D board of characters (list of lists) and a list of words.
  • Output: A list of words found in the board.
  • Constraints: The board size can be up to 200 x 200, and the number of words can be up to 10^3. The words can have a maximum length of 10^3.

To solve this problem, we can use the backtracking algorithm. We'll iterate through each cell of the board and start a backtracking search from that cell for each word in the word list. We'll keep track of the visited cells to avoid revisiting them in the same word search.

Design an algorithm

  • Create a helper function called search_word that takes the board, current cell indices, current word, and the index of the character being checked in the word.
    • If the index is equal to the length of the word, it means we have found the complete word. Add it to the result list.
    • If the cell indices are out of bounds or the character in the cell doesn't match the character in the word at the current index, return.
    • Mark the current cell as visited (you can use a special character or change it to an empty space to avoid revisiting).
    • Recursively call search_word for the neighboring cells (up, down, left, right) with the updated word index.
    • Mark the current cell as unvisited.
  • Iterate through each cell in the board:
    • For each word in the word list, call the search_word function with the current cell and the word.

Approach explanation

We'll implement the backtracking algorithm to search for words in the board. We'll start a backtracking search from each cell for each word in the word list. If the current character in the cell matches the character in the word, we'll explore its neighboring cells recursively. We'll keep track of visited cells to avoid revisiting them in the same word search.

Implementation

def findWords(board, words):
    def search_word(i, j, word, idx):
        if idx == len(word):
            result.add(word)
            return

        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[idx]:
            return

        temp = board[i][j]
        board[i][j] = "#"  # Mark cell as visited

        search_word(i+1, j, word, idx+1)
        search_word(i-1, j, word, idx+1)
        search_word(i, j+1, word, idx+1)
        search_word(i, j-1, word, idx+1)

        board[i][j] = temp  # Mark cell as unvisited

    result = set()
    for i in range(len(board)):
        for j in range(len(board[0])):
            for word in words:
                search_word(i, j, word, 0)
    
    return list(result)

Test your code

Here are some test cases you can use to verify the correctness of your code

# Test case 1
board = [
    ['o', 'a', 'a', 'n'],
    ['e', 't', 'a', 'e'],
    ['i', 'h', 'k', 'r'],
    ['i', 'f', 'l', 'v']
]
words = ["oath", "pea", "eat", "rain"]
# Expected output: ["oath", "eat"]

# Test case 2
board = [
    ['a', 'b'],
    ['c', 'd']
]
words = ["ab", "ac", "bd", "abcd"]
# Expected output: ["ab", "ac", "bd"]

# Test case 3
board = [['a']]
words = ["a"]
# Expected output: ["a"]

Optimization

The solution provided has a time complexity of O(NM4^K), where N and M are the dimensions of the board, and K is the average length of the words. We can optimize the solution further by using a Trie data structure to store the words. This way, we can efficiently prune the search if the current prefix doesn't match any word in the Trie.

Error handling

The code assumes that the input is valid, i.e., the board and words list are not empty, and the board is a valid 2D list.

Complexity analysis

  • Time complexity: O(NM4^K), where N and M are the dimensions of the board, and K is the average length of the words. This is because for each cell in the board, we perform up to 4 recursive calls, each exploring the neighboring cells. The worst-case scenario occurs when we explore all cells for each word in the word list.
  • Space complexity: O(K), where K is the length of the longest word. This is the space used for the recursive call stack during backtracking.

The optimized solution with a Trie data structure would have a slightly improved time complexity of O(NM4^L), where L is the length of the longest word in the Trie.

Next Post Previous Post