Close Menu
    What's Hot
    Explore the coolest frontend learning platform !
    Visit NamasteDev
    Thursday, June 4

    Word Search

    Updated: Algorithms No Comments4 Mins Readdevangini123By

    Problem Statement:

    Given an m x n grid of characters board and a string word, return true if word exists in the grid.

    The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

    Example 1:

    Input: board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED”

    Output: true

    Example 2:

    Input: board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “SEE”

    Output: true

    Example 3:

    Input: board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCB”

    Output: false

    Constraints

    • m == board.length
    • n = board[i].length
    • 1 <= m, n <= 6
    • 1 <= word.length <= 15
    • board and word consists of only lowercase and uppercase English letters.

    Approach

    • Traverse the board cell by cell.
    • Whenever the first character of the word matches, start a DFS backtracking search from that cell.
    • In DFS:
      • Mark the current cell as visited ("#").
      • Explore all 4 directions (up, down, left, right) if the next character matches.
      • If you reach the end of the word, return true.
      • Restore the cell after exploring (backtrack).
    • If any DFS path finds the word, return true; otherwise return false.

    Dry Run

    Input:

    board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]
word = "ABCCED"

    State Transitions:

    Initialize:
result = false
m = 3, n = 4

Outer loop:
i = 0, j = 0 → board[0][0] = "A" matches word[0] = "A"
→ Call backtrack(0, 0, 1)

Level 1:
(x=0, y=0, nextIndex=1, looking for "B")
original = "A", board[0][0] = "#"
Right: board[0][1] = "B" → matches word[1]
→ Call backtrack(0, 1, 2)

Level 2:
(x=0, y=1, nextIndex=2, looking for "C")
original = "B", board[0][1] = "#"
Right: board[0][2] = "C" → matches word[2]
→ Call backtrack(0, 2, 3)

Level 3:
(x=0, y=2, nextIndex=3, looking for "C")
original = "C", board[0][2] = "#"
Down: board[1][2] = "C" → matches word[3]
→ Call backtrack(1, 2, 4)

Level 4:
(x=1, y=2, nextIndex=4, looking for "E")
original = "C", board[1][2] = "#"
Down: board[2][2] = "E" → matches word[4]
→ Call backtrack(2, 2, 5)

Level 5:
(x=2, y=2, nextIndex=5, looking for "D")
original = "E", board[2][2] = "#"
Left: board[2][1] = "D" → matches word[5]
→ Call backtrack(2, 1, 6)

Level 6:
(x=2, y=1, nextIndex=6)
nextIndex == word.length → result = true

Backtracking restores all modified cells as recursion unwinds.

    Final Output: true

    Explanation: The algorithm performs DFS + backtracking:

    • Starts at "A" (0,0) and recursively explores neighbors.
    • Marks visited cells as "#" to avoid revisiting during the same path.
    • Successfully forms the word "ABCCED".
    • Once nextIndex === word.length, result becomes true.

    
var exist = function(board, word) {
    let result = false;
    let m = board.length;
    let n = board[0].length;
    let backtrack = (x, y, nextIndex) => {
        if(nextIndex === word.length) {
            result = true;
        }
        let original = board[x][y];
        board[x][y] = "#";
        if(y < n-1 && board[x][y+1] === word[nextIndex]) {
            backtrack(x, y+1, nextIndex + 1);
        }
        if(y > 0 && board[x][y-1] === word[nextIndex]) {
            backtrack(x, y-1, nextIndex + 1);
        } 
        if(x > 0 && board[x-1][y] === word[nextIndex]) {
            backtrack(x-1, y, nextIndex + 1);
        }
        if(x < m-1 && board[x+1][y] === word[nextIndex]) {
            backtrack(x+1, y, nextIndex + 1);
        }
        board[x][y] = original;
    }
    for(let i=0; i < m; i++){
        for(let j=0; j < n; j++){
            if(board[i][j] === word[0]) {
                backtrack(i, j, 1)
            }
        }
    }
    return result;
};

    
class Solution:
    def exist(self, board, word: str) -> bool:
        m, n = len(board), len(board[0])
        self.result = False

        def backtrack(x, y, nextIndex):
            if nextIndex == len(word):
                self.result = True
                return
            original = board[x][y]
            board[x][y] = "#"

            if y < n-1 and board[x][y+1] == word[nextIndex]:
                backtrack(x, y+1, nextIndex+1)
            if y > 0 and board[x][y-1] == word[nextIndex]:
                backtrack(x, y-1, nextIndex+1)
            if x > 0 and board[x-1][y] == word[nextIndex]:
                backtrack(x-1, y, nextIndex+1)
            if x < m-1 and board[x+1][y] == word[nextIndex]:
                backtrack(x+1, y, nextIndex+1)

            board[x][y] = original

        for i in range(m):
            for j in range(n):
                if board[i][j] == word[0]:
                    backtrack(i, j, 1)
                    if self.result:
                        return True
        return self.result

    
class Solution {
    boolean result = false;

    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;

        for (int i=0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word.charAt(0)) {
                    backtrack(board, word, i, j, 1);
                    if (result) return true;
                }
            }
        }
        return result;
    }

    private void backtrack(char[][] board, String word, int x, int y, int nextIndex) {
        if (nextIndex == word.length()) {
            result = true;
            return;
        }
        char original = board[x][y];
        board[x][y] = '#';

        if (y < board[0].length-1 && board[x][y+1] == word.charAt(nextIndex)) backtrack(board, word, x, y+1, nextIndex+1);
        if (y > 0 && board[x][y-1] == word.charAt(nextIndex)) backtrack(board, word, x, y-1, nextIndex+1);
        if (x > 0 && board[x-1][y] == word.charAt(nextIndex)) backtrack(board, word, x-1, y, nextIndex+1);
        if (x < board.length-1 && board[x+1][y] == word.charAt(nextIndex)) backtrack(board, word, x+1, y, nextIndex+1);

        board[x][y] = original;
    }
}

    
class Solution {
public:
    bool exist(vector>& board, string word) {
        int m = board.size(), n = board[0].size();
        bool result = false;

        function backtrack = [&](int x, int y, int nextIndex) {
            if (nextIndex == word.size()) {
                result = true;
                return;
            }
            char original = board[x][y];
            board[x][y] = '#';

            if (y < n-1 && board[x][y+1] == word[nextIndex]) backtrack(x, y+1, nextIndex+1);
            if (y > 0 && board[x][y-1] == word[nextIndex]) backtrack(x, y-1, nextIndex+1);
            if (x > 0 && board[x-1][y] == word[nextIndex]) backtrack(x-1, y, nextIndex+1);
            if (x < m-1 && board[x+1][y] == word[nextIndex]) backtrack(x+1, y, nextIndex+1);

            board[x][y] = original;
        };

        for (int i=0; i < m; i++) {
            for (int j=0; j < n; j++) {
                if (board[i][j] == word[0]) {
                    backtrack(i, j, 1);
                    if (result) return true;
                }
            }
        }
        return result;
    }
};

    
bool backtrack(char** board, int m, int n, int x, int y, const char* word, int nextIndex) {
    if (word[nextIndex] == '\0') return true;
    char original = board[x][y];
    board[x][y] = '#';

    if (y < n-1 && board[x][y+1] == word[nextIndex] && backtrack(board,m,n,x,y+1,word,nextIndex+1)) return true;
    if (y > 0 && board[x][y-1] == word[nextIndex] && backtrack(board,m,n,x,y-1,word,nextIndex+1)) return true;
    if (x > 0 && board[x-1][y] == word[nextIndex] && backtrack(board,m,n,x-1,y,word,nextIndex+1)) return true;
    if (x < m-1 && board[x+1][y] == word[nextIndex] && backtrack(board,m,n,x+1,y,word,nextIndex+1)) return true;

    board[x][y] = original;
    return false;
}

bool exist(char** board, int m, int* nCols, char* word) {
    int n = nCols[0];
    for (int i=0; i < m; i++) {
        for (int j=0; j < n; j++) {
            if (board[i][j] == word[0]) {
                if (backtrack(board, m, n, i, j, word, 1)) return true;
            }
        }
    }
    return false;
}

    
public class Solution {
    public bool Exist(char[][] board, string word) {
        int m = board.Length, n = board[0].Length;
        bool result = false;

        void Backtrack(int x, int y, int nextIndex) {
            if (nextIndex == word.Length) {
                result = true;
                return;
            }
            char original = board[x][y];
            board[x][y] = '#';

            if (y < n-1 && board[x][y+1] == word[nextIndex]) Backtrack(x, y+1, nextIndex+1);
            if (y > 0 && board[x][y-1] == word[nextIndex]) Backtrack(x, y-1, nextIndex+1);
            if (x > 0 && board[x-1][y] == word[nextIndex]) Backtrack(x-1, y, nextIndex+1);
            if (x < m-1 && board[x+1][y] == word[nextIndex]) Backtrack(x+1, y, nextIndex+1);

            board[x][y] = original;
        }

        for (int i=0; i < m; i++) {
            for (int j=0; j < n; j++) {
                if (board[i][j] == word[0]) {
                    Backtrack(i, j, 1);
                    if (result) return true;
                }
            }
        }
        return result;
    }
}

    Keep Reading

    Add A Comment
    Leave A Reply

    Demo

    Courses

    Community

    Contact Us