Word Search

Real Life Intuition

To solve this problem in real life, imagine being in a grid-like garden where each cell contains a different flower with a letter on it. The goal is to trace a path through adjacent flowers to spell out a given word. Starting from each flower that matches the first letter of the word, inspect neighboring flowers in all four directions (up, down, left, right). Temporarily mark each flower as visited to avoid revisiting it, and backtrack if the current path does not lead to the complete word, restoring the garden's state for subsequent attempts. This process continues until the word is found or all possibilities are exhausted.

Recursive Process Intuition

The recursive process mimics this real-life approach. Begin at any cell matching the first letter of the word. Recursively explore adjacent cells for the next letter. Temporarily mark cells as visited to avoid repetition. If a path spells out the word, return true. If not, go back by unmarking the cell and continue exploring other paths. This continues until all possible paths from each starting cell are checked.

Approach

Start by iterating through each cell in the grid.
For each cell, check if it matches the first character of the word. f it matches, invoke a helper function to explore all possible paths from this cell.
In the helper function, perform the following checks:
- Check if the current index matches the length of the word, indicating the word is found.
- Check boundary conditions and character mismatch to prevent invalid accesses.
If the character matches, mark the current cell as visited by temporarily changing its value. Recursively explore all four directions (up, down, left, right) from the current cell for the next character in the word. If any recursive call returns true, propagate this result up the call stack.
After exploring all directions, restore the current cell's original value to allow other paths to use it. Continue this process until all cells and paths are exhausted.
Return true if any path successfully spells out the word; otherwise, return false.

Dry Run

Solution

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Helper function to check if the word exists starting from cell (i, j)
    bool func(vector<vector<char> > & v, int i, int j, string& s, int k) {
        // If all characters of the word are found
        if (k == s.length()) {
            return true;
        }
        // Boundary conditions and character mismatch check
        if (i < 0 || j < 0 || i >= v.size() || j >= v[0].size() || s[k] != v[i][j]) {
            return false;
        }

        // Initialize answer as false
        bool ans = false;

        // Temporarily mark the cell as visited
        char x = v[i][j];
        v[i][j] = ' ';

        // Check all four possible directions (down, up, right, left)
        ans |= func(v, i + 1, j, s, k + 1);
        ans |= func(v, i - 1, j, s, k + 1);
        ans |= func(v, i, j + 1, s, k + 1);
        ans |= func(v, i, j - 1, s, k + 1);

        // Restore the original character in the cell
        v[i][j] = x;
        
        return ans;
    }

    // Main function to check if the word exists in the board
    bool exist(vector<vector<char> >& board, string word) {
        // Iterate through each cell in the board
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                // If the first character matches, start the search
                if (board[i][j] == word[0]) {
                    // If the word is found, return true
                    if (func(board, i, j, word, 0)) {
                        return true;
                    }
                }
            }
        }
        // If the word is not found, return false
        return false;
    }
};

// Main function to test the solution
int main() {
    Solution sol;
    vector<vector<char> > board = {
        {'A', 'B', 'C', 'E'},
        {'S', 'F', 'C', 'S'},
        {'A', 'D', 'E', 'E'}
    };
    string word = "ABCCED";
    
    if (sol.exist(board, word)) {
        cout << "Word found!" << endl;
    } else {
        cout << "Word not found!" << endl;
    }

    return 0;
}
class Solution {
    // Helper function to check if the word exists starting from cell (i, j)
    private boolean func(char[][] board, int i, int j, String word, int k) {
        // If all characters of the word are found
        if (k == word.length()) {
            return true;
        }
        // Boundary conditions and character mismatch check
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || word.charAt(k) != board[i][j]) {
            return false;
        }

        // Temporarily mark the cell as visited
        char temp = board[i][j];
        board[i][j] = ' ';

        // Check all four possible directions (down, up, right, left)
        boolean ans = func(board, i + 1, j, word, k + 1) ||
                      func(board, i - 1, j, word, k + 1) ||
                      func(board, i, j + 1, word, k + 1) ||
                      func(board, i, j - 1, word, k + 1);

        // Restore the original character in the cell
        board[i][j] = temp;

        return ans;
    }

    // Main function to check if the word exists in the board
    public boolean exist(char[][] board, String word) {
        // Iterate through each cell in the board
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // If the first character matches, start the search
                if (board[i][j] == word.charAt(0)) {
                    // If the word is found, return true
                    if (func(board, i, j, word, 0)) {
                        return true;
                    }
                }
            }
        }
        // If the word is not found, return false
        return false;
    }

    // Main method to test the solution
    public static void main(String[] args) {
        Solution solution = new Solution();
        char[][] board = {
            {'A', 'B', 'C', 'E'},
            {'S', 'F', 'C', 'S'},
            {'A', 'D', 'E', 'E'}
        };
        String word = "ABCCED";

        if (solution.exist(board, word)) {
            System.out.println("Word found!");
        } else {
            System.out.println("Word not found!");
        }
    }
}
class Solution:
    # Helper function to check if the word exists starting from cell (i, j)
    def func(self, board, i, j, word, k):
        # If all characters of the word are found
        if k == len(word):
            return True
        # Boundary conditions and character mismatch check
        if i < 0 or j < 0 or i >= len(board) or j >= len(board[0]) or word[k] != board[i][j]:
            return False

        # Temporarily mark the cell as visited
        temp = board[i][j]
        board[i][j] = ' '

        # Check all four possible directions (down, up, right, left)
        ans = (self.func(board, i + 1, j, word, k + 1) or
               self.func(board, i - 1, j, word, k + 1) or
               self.func(board, i, j + 1, word, k + 1) or
               self.func(board, i, j - 1, word, k + 1))

        # Restore the original character in the cell
        board[i][j] = temp
        
        return ans

    # Main function to check if the word exists in the board
    def exist(self, board, word):
        # Iterate through each cell in the board
        for i in range(len(board)):
            for j in range(len(board[0])):
                # If the first character matches, start the search
                if board[i][j] == word[0]:
                    # If the word is found, return true
                    if self.func(board, i, j, word, 0):
                        return True
        # If the word is not found, return False
        return False

# Main function to test the solution
solution = Solution()
board = [
    ['A', 'B', 'C', 'E'],
    ['S', 'F', 'C', 'S'],
    ['A', 'D', 'E', 'E']
]
word = "ABCCED"

if solution.exist(board, word):
    print("Word found!")
else:
    print("Word not found!")
class Solution {
    // Helper function to check if the word exists starting from cell (i, j)
    func(board, i, j, word, k) {
        // If all characters of the word are found
        if (k === word.length) {
            return true;
        }
        // Boundary conditions and character mismatch check
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || word[k] !== board[i][j]) {
            return false;
        }

        // Temporarily mark the cell as visited
        let temp = board[i][j];
        board[i][j] = ' ';

        // Check all four possible directions (down, up, right, left)
        let ans = this.func(board, i + 1, j, word, k + 1) ||
                  this.func(board, i - 1, j, word, k + 1) ||
                  this.func(board, i, j + 1, word, k + 1) ||
                  this.func(board, i, j - 1, word, k + 1);

        // Restore the original character in the cell
        board[i][j] = temp;
        
        return ans;
    }

    // Main function to check if the word exists in the board
    exist(board, word) {
        // Iterate through each cell in the board
        for (let i = 0; i < board.length; i++) {
            for (let j = 0; j < board[0].length; j++) {
                // If the first character matches, start the search
                if (board[i][j] === word[0]) {
                    // If the word is found, return true
                    if (this.func(board, i, j, word, 0)) {
                        return true;
                    }
                }
            }
        }
        // If the word is not found, return false
        return false;
    }
}

// Main function to test the solution
const solution = new Solution();
const board = [
    ['A', 'B', 'C', 'E'],
    ['S', 'F', 'C', 'S'],
    ['A', 'D', 'E', 'E']
];
const word = "ABCCED";

if (solution.exist(board, word)) {
    console.log("Word found!");
} else {
    console.log("Word not found!");
}

Complexity Analysis

Time Complexity : O(N * M * 4^L) where N is rows, M is columns and L is the word length; recursive search through board.

Space Complexity : O(L) due to recursive call stack depth, where L is the length of the word.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Real Life Intuition

Recursive Process Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code