Word Search: Traversing a Letter Grid to Form Words

The "Word Search" problem involves searching for a specific word in a grid of letters, where the word can be formed by connecting letters horizontally or vertically.

Problem Statement

Given a 2D board of letters and a word, check if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are those horizontally or vertically neighboring.

Example

• Input: Board:

[
  ["A", "B", "C", "E"],
  ["S", "F", "C", "S"],
  ["A", "D", "E", "E"]
]

Word: "ABCCED"

• Output: true

Solution Approach (typescript)

function exist(board: string[][], word: string): boolean {
  function dfs(board: string[][], i: number, j: number, count: number, word: string): boolean {
    if (count === word.length) return true;
    if (
      i < 0 ||
      i >= board.length ||
      j < 0 ||
      j >= board[i].length ||
      board[i][j] !== word[count]
    ) {
      return false;
    }

    let temp = board[i][j];
    board[i][j] = " ";
    let found =
      dfs(board, i + 1, j, count + 1, word) ||
      dfs(board, i - 1, j, count + 1, word) ||
      dfs(board, i, j + 1, count + 1, word) ||
      dfs(board, i, j - 1, count + 1, word);

    board[i][j] = temp;
    return found;
  }

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[i].length; j++) {
      if (board[i][j] === word[0] && dfs(board, i, j, 0, word)) {
        return true;
      }
    }
  }
  return false;
}

Breaking Down the Solution

• Depth-First Search (DFS): Use DFS to traverse the board, exploring each possible path.
• Check Each Cell: Start from each cell that matches the first letter of the word, and recursively check its neighbors.
• Track Progress: Temporarily mark cells as visited during each DFS iteration to avoid revisiting them in the same path.
• Return Result: If the word is found, return true; if the board is fully explored without finding the word, return false.

Solution in Go

package main

import (
	"fmt"
)

func exist(board [][]byte, word string) bool {
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[i]); j++ {
			if dfs(board, i, j, word, 0) {
				return true
			}
		}
	}
	return false
}

func dfs(board [][]byte, i, j int, word string, count int) bool {
	if count == len(word) {
		return true
	}
	if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) || board[i][j] != word[count] {
		return false
	}

	temp := board[i][j]
	board[i][j] = byte(' ')
	found := dfs(board, i+1, j, word, count+1) ||
		dfs(board, i-1, j, word, count+1) ||
		dfs(board, i, j+1, word, count+1) ||
		dfs(board, i, j-1, word, count+1)

	board[i][j] = temp
	return found
}

func main() {
	board := [][]byte{
		{'A', 'B', 'C', 'E'},
		{'S', 'F', 'C', 'S'},
		{'A', 'D', 'E', 'E'},
	}
	word := "ABCCED"
	fmt.Println(exist(board, word)) // Output: true
}

In this Go implementation:

• The exist function checks if a given word exists in the board. It iterates over each cell in the board and calls the dfs (Depth-First Search) function.
• The dfs function performs a depth-first search from the current cell to check if the remaining characters of the word can be formed. It marks the cell as visited by replacing the character with a space and then recursively checks adjacent cells.
• If dfs returns true at any point, exist will return true, indicating the word is found in the board.
• After the recursive call, the cell's original character is restored.

Solution in C++

#include <iostream>
#include <vector>

using namespace std;

bool dfs(vector<vector<char>>& board, int i, int j, string& word, int count) {
    if (count == word.length()) {
        return true;
    }
    if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != word[count]) {
        return false;
    }

    char temp = board[i][j];
    board[i][j] = ' ';
    bool found = dfs(board, i + 1, j, word, count + 1)
              || dfs(board, i - 1, j, word, count + 1)
              || dfs(board, i, j + 1, word, count + 1)
              || dfs(board, i, j - 1, word, count + 1);

    board[i][j] = temp;
    return found;
}

bool exist(vector<vector<char>>& board, string word) {
    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board[i].size(); j++) {
            if (board[i][j] == word[0] && dfs(board, i, j, word, 0)) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    vector<vector<char>> board = {
        {'A','B','C','E'},
        {'S','F','C','S'},
        {'A','D','E','E'}
    };
    string word = "ABCCED";

    cout << (exist(board, word) ? "true" : "false") << endl;

    return 0;
}

In this C++ solution:

• The dfs function performs a depth-first search from the current cell, recursively checking adjacent cells to form the word. It temporarily marks the cell as visited by setting it to a space character and restores it after the recursive calls.
• The exist function iterates over each cell in the board, starting a new DFS search whenever it finds the first character of the word.
• If dfs returns true for any starting cell, the entire function returns true, indicating the word is found.
• Compile and run this program to check if the given word exists in the board.

Solution in Python

def exist(board, word):
    def dfs(board, i, j, word, count):
        if count == len(word):
            return True
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[count]:
            return False

        temp = board[i][j]
        board[i][j] = ' '  # Mark as visited
        found = dfs(board, i + 1, j, word, count + 1) or \
                dfs(board, i - 1, j, word, count + 1) or \
                dfs(board, i, j + 1, word, count + 1) or \
                dfs(board, i, j - 1, word, count + 1)

        board[i][j] = temp  # Reset the state
        return found

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

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

In this Python solution:

• The dfs function is defined within exist to utilize the scope of board and word. It performs a depth-first search from the current cell.
• The cell is temporarily marked as visited by setting it to a space character, and then restored to its original value after the recursive calls.
• exist iterates over the board, calling dfs for each cell that matches the first letter of the word.
• If dfs returns True, the word exists in the board; otherwise, it does not.

Solution in Java

public class WordSearch {
    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == word.charAt(0) && dfs(board, i, j, 0, word)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, int i, int j, int count, String word) {
        if (count == word.length()) return true;
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(count)) return false;

        char temp = board[i][j];
        board[i][j] = ' '; // Mark as visited
        boolean found = dfs(board, i + 1, j, count + 1, word)
                     || dfs(board, i - 1, j, count + 1, word)
                     || dfs(board, i, j + 1, count + 1, word)
                     || dfs(board, i, j - 1, count + 1, word);

        board[i][j] = temp; // Reset state
        return found;
    }

    public static void main(String[] args) {
        WordSearch solution = new WordSearch();
        char[][] board = {
            {'A', 'B', 'C', 'E'},
            {'S', 'F', 'C', 'S'},
            {'A', 'D', 'E', 'E'}
        };
        String word = "ABCCED";
        System.out.println(solution.exist(board, word)); // Output: true
    }
}

In this Java solution:

• The exist method iterates over each cell in the board, starting a DFS search from cells that match the first character of the word.
• The dfs method performs a depth-first search to check if the word can be formed, starting from the current cell. It marks the cell as visited by setting it to a space character and resets it to its original value after exploring all possible paths from that cell.
• If dfs returns true at any point, exist will return true, indicating that the word is found in the board.
• The main method demonstrates how to use the WordSearch class with a sample board and word.

Solution in Kotlin

class WordSearch {
    fun exist(board: Array<CharArray>, word: String): Boolean {
        for (i in board.indices) {
            for (j in board[0].indices) {
                if (board[i][j] == word[0] && dfs(board, i, j, 0, word)) {
                    return true
                }
            }
        }
        return false
    }

    private fun dfs(board: Array<CharArray>, i: Int, j: Int, count: Int, word: String): Boolean {
        if (count == word.length) return true
        if (i < 0 || i >= board.size || j < 0 || j >= board[0].size || board[i][j] != word[count]) return false

        val temp = board[i][j]
        board[i][j] = ' '  // Mark as visited
        val found = dfs(board, i + 1, j, count + 1, word)
                  || dfs(board, i - 1, j, count + 1, word)
                  || dfs(board, i, j + 1, count + 1, word)
                  || dfs(board, i, j - 1, count + 1, word)

        board[i][j] = temp  // Reset state
        return found
    }
}

fun main() {
    val solution = WordSearch()
    val board = arrayOf(
        charArrayOf('A', 'B', 'C', 'E'),
        charArrayOf('S', 'F', 'C', 'S'),
        charArrayOf('A', 'D', 'E', 'E')
    )
    val word = "ABCCED"
    println(solution.exist(board, word)) // Output: true
}

In this Kotlin solution:

• The exist function iterates over each cell in the board, starting a DFS search from cells that match the first character of the word.
• The dfs function performs a depth-first search to check if the word can be formed, starting from the current cell. It marks the cell as visited by setting it to a space character and resets it to its original value after the recursive calls.
• If dfs returns true for any starting cell, exist will return true, indicating the word is found in the board.
• The main function demonstrates how to use the WordSearch class with a sample board and word.

Conclusion

The Word Search problem is a classic example of using DFS in a matrix-like structure. It tests one's ability to implement recursive search algorithms and handle edge cases in grid traversal.