Word Search

1. Clarify the problem:

   • The problem requires us to determine if a given word exists in a 2D board of characters.
   • The word can be constructed by connecting adjacent letters horizontally or vertically.
   • We need to return True if the word exists in the board, and False otherwise.
   • The input board consists of uppercase and lowercase English letters.
   • The word may contain both uppercase and lowercase letters.
   • The length of the word can range from 1 to 15.
   • The size of the board can range from 1x1 to 200x200.

2. Analyze the problem:

   • Input: A 2D board of characters and a word.
   • Output: True if the word exists in the board, False otherwise.
   • Constraints:
     • The input board consists of uppercase and lowercase English letters.
     • The word may contain both uppercase and lowercase letters.
     • The length of the word can range from 1 to 15.
     • The size of the board can range from 1x1 to 200x200.

3. Design an algorithm:

   • We can solve this problem using a backtracking approach.
   • We start by iterating through the board to find the first character of the word.
   • For each occurrence of the first character, we perform a depth-first search (DFS) to check if the word can be formed from that position.
   • In the DFS, we explore the neighboring cells to find the next character of the word.
   • If the next character is found, we continue the DFS from that position.
   • We mark visited cells to avoid revisiting them during the DFS.
   • If we successfully find all the characters of the word, we return True.
   • If we exhaust all the possibilities without finding the complete word, we return False.

4. Explain your approach:

   • We will perform a depth-first search (DFS) on the board to find the given word.
   • We will iterate through the board to find the first character of the word.
   • For each occurrence of the first character, we will start the DFS.
   • In the DFS, we will check if the current position matches the corresponding character of the word.
   • If it matches, we will mark the current position as visited and recursively explore the neighboring cells.
   • We will continue the DFS until we find the complete word or exhaust all possibilities.
   • If we find the complete word, we will return True.
   • If we exhaust all possibilities without finding the complete word, we will return False.

5. Write clean and readable code:

python

def exist(board, word):
    rows, cols = len(board), len(board[0])
    for i in range(rows):
        for j in range(cols):
            if dfs(board, word, i, j, 0):
                return True
    return False

def dfs(board, word, row, col, index):
    if index == len(word):
        return True

    if (
        row < 0
        or col < 0
        or row >= len(board)
        or col >= len(board[0])
        or board[row][col] != word[index]
    ):
        return False

    temp = board[row][col]
    board[row][col] = '#'  # Mark the cell as visited

    if (
        dfs(board, word, row - 1, col, index + 1)
        or dfs(board, word, row + 1, col, index + 1)
        or dfs(board, word, row, col - 1, index + 1)
        or dfs(board, word, row, col + 1, index + 1)
    ):
        return True

    board[row][col] = temp  # Reset the cell to its original value
    return False

6. Test your code:

   • Test case 1: board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED"

     • In this test case, the word "ABCCED" can be formed by starting from the top-left corner of the board.
     • The function should return True.

   • Test case 2: board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "SEE"

     • In this test case, the word "SEE" can be formed by starting from the second row, second column of the board.
     • The function should return True.

   • Test case 3: board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCB"

     • In this test case, the word "ABCB" cannot be formed from the given board.
     • The function should return False.

python

board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']]
word = "ABCCED"
print(exist(board, word))  # Output: True

board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']]
word = "SEE"
print(exist(board, word))  # Output: True

board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']]
word = "ABCB"
print(exist(board, word))  # Output: False

7. Optimize if necessary:

   • The backtracking approach used in the algorithm has a time complexity of O(M * N * 4^L), where M is the number of rows, N is the number of columns, and L is the length of the word.
   • The space complexity is O(L) for the recursion stack.

8. Handle error cases:

   • The given code assumes the input is valid and doesn't explicitly handle error cases like empty board or empty word. Additional error handling logic can be added to validate the input.

9. Discuss complexity analysis:

   • Time complexity: O(M * N * 4^L), where M is the number of rows, N is the number of columns, and L is the length of the word.
   • Space complexity: O(L) for the recursion stack.