Word Search Grid Traversal

Given an m x n matrix(2d array) of characters and a string called "word," determine whether the word can be formed by sequentially traversing adjacent cells in the grid.

Adjacent cells are those that are horizontally or vertically neighbouring, and each cell may be used at most once to form the word. Return true if the word can be constructed from the grid, otherwise return false.

Example 1

Input :

board = [  ["A","B","C","E"],

                ["S","F","C","S"],

                ["A","D","E","E"]  ]

word = "ASFC"

Output: true

Example 2

Input :

board = [  ["A","B","C","E"],

                ["S","F","C","S"],

                ["A","D","E","E"]  ]

word = "ABFS"

Output : true

Approach

The Word Search problem can be elegantly solved using recursion. The idea is to systematically explore each cell of the board, checking if the current cell and word character match. If they match, we recursively explore neighboring cells to see if they can form the rest of the word.

The process involves iterating over each cell of the board and each character of the word from the beginning. We check if the current character of the word matches the character at the corresponding position in the board. If it does, we recursively explore its neighboring cells to see if they can form the rest of the word. If a match is not found, we move on to the next character in the word and repeat the process.

This approach effectively explores all possible paths on the board, ensuring that the word can be formed from sequentially adjacent cells while avoiding revisiting any cell more than once.

Steps

1. Check for edge cases: Before starting the search, make sure that the board and the word are not null or empty. If any of them is, return false.
2. Initialize variables: Get the dimensions of the board, namely m and n.
3. Iterate through the board: Loop through each cell of the board.
4. Depth-First Search (DFS): For each cell in the board, perform a DFS to check if the current cell and its neighbours can form the word.

1. In the DFS function, the base case is when the index of the word reaches its length, indicating that the entire word has been found. Return true in this case.
2. Check if the current cell is out of bounds or does not match the character of the word at the current index. If so, return false.
3. Temporarily mark the current cell as visited (e.g., change its character to a non-alphabetic character) to avoid re-visiting it during the search.
4. Recursively call DFS for the neighboring cells (up, down, left, right) with the next character of the word. If any of these recursive calls return true, then return true.
5. Restore the original character of the current cell before returning from the DFS function.

5. Return result: If no match is found after looping through all cells, return false.

Complexity

• Time Complexity: O(m * n * 4^k), where m is the number of rows, n is the number of columns, and k is the length of the word.
• Space Complexity: O(k), where k is the length of the word

Code

public class WordSearch
{
    public boolean exist(char[][] board, String word)
    {
        if (board == null || board.length == 0 || word == null || word.length() == 0)
            return false;

        int m = board.length;
        int n = board[0].length;

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (dfs(board, i, j, word, 0))
                    return true;
            }
        }

        return false;
    }

    private boolean dfs(char[][] board, int i, int j, String word, int index)
    {
        if (index == word.length())
            return true;

        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(index))
            return false;

        char temp = board[i][j];
        board[i][j] = ' ';


        boolean found = dfs(board, i + 1, j, word, index + 1) ||
                        dfs(board, i - 1, j, word, index + 1) ||
                        dfs(board, i, j + 1, word, index + 1) ||
                        dfs(board, i, j - 1, word, index + 1);


        board[i][j] = temp;

        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 word1 = "ASFC";
        String word2 = "ABFS";

        System.out.println("Output for ASFC: " + solution.exist(board, word1));
        System.out.println("Output for ABFS: " + solution.exist(board, word2));
    }
}

Output

Output for ASFC: true
Output for ABFS: true