blind75

Word Search: Traversing a Letter Grid to Form Words

Jan 13, 2024 · Solving the Word Search problem by finding a path through a grid of letters to form a specific word, either horizontally or vertically.

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)

typescript

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

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.

Rust Solution

rust

Rust's &str can't be indexed by position, so word.chars().collect() pre-materialises the word into a Vec<char> that dfs then borrows as &[char] and reads with a usize count. Coordinates are carried as i32 precisely because i - 1 can go negative — the bounds check runs while i/j are still signed, and only after it passes does let bi = i as usize produce an index, since a usize can't hold a negative or silently yield undefined the way a JS negative index would (it would panic instead). The grid is threaded through as &mut Vec<Vec<char>>, so the board[bi][bj] = ' ' marking and its restore mutate in place across the recursion, and exist/dfs finish on the bare expressions false and found rather than an explicit return.

Comments (0)

Stub — comments live in your browser only (localStorage). No server round-trip yet.

No comments yet. Be the first.