Word Search - Check if a word exists in a grid or not

Last Updated : 29 Sep, 2025

Given a 2D array mat[][] of characters and a string word, check whether the word exists in the array or not. The word can be matched in four possible directions: horizontally left or right, and vertically up or down. Each cell can be used only once in forming the word.

Examples: 

Input: mat[][] = [['T', 'E', 'E'], ['S', 'G', 'K'], ['T', 'E', 'L']], word = "GEEK"
Output: true
Explanation: Word "GEEK" can be found in the given grid as follows

geek

Input: mat[][] = [['T', 'E', 'U'], ['S', 'G', 'K'], ['T', 'E', 'L']], word = "GEEK"
Output: false
Explanation: Word "GEEK" cannot be found in the given grid.

geeks
Try it on GfG Practice
redirect icon

[Approach] Using Recursion and Backtracking

The idea is to search for the word in the grid by exploring all possible paths. For every cell that matches the first character of the word, we recursively explore in four directions — up, down, left, and right — to check if the entire word can be formed. We mark cells as visited temporarily during the search to avoid revisiting the same cell in the current path, and backtrack after exploring all possibilities from that cell.

Working:


C++ 
#include <iostream>
#include <vector>
using namespace std;

// Recursive Function to check if the word exists in the matrix or not
bool findMatch(vector<vector<char>> &mat, string &word, int x, int y, int wIdx) {
    int wLen = word.length();
	int n = mat.size();
  	int m = mat[0].size();
    if (wIdx == wLen)
        return true;

    // Out of Boundary
    if (x < 0 || y < 0 || x >= n || y >= m)
        return false;

    // If grid matches with a letter while
    // recursion
    if (mat[x][y] == word[wIdx]) {

        // Marking this cell as visited
        char temp = mat[x][y];
        mat[x][y] = '#';

        // finding subpattern in 4 directions
        bool res = findMatch(mat, word, x - 1, y, wIdx + 1) ||
                   findMatch(mat, word, x + 1, y, wIdx + 1) ||
                   findMatch(mat, word, x, y - 1, wIdx + 1) ||
                   findMatch(mat, word, x, y + 1, wIdx + 1);

       
        mat[x][y] = temp;
        return res;
    }
  	
    return false;
}

// Function to check if the word exists in the matrix or not
bool isWordExist(vector<vector<char>> &mat, string &word) {
    int wLen = word.length();
	int n = mat.size();
  	int m = mat[0].size();
  
    // if total characters in matrix is
    // less than word length
    if (wLen > n * m)
        return false;
        
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {

            // If first letter matches, then recur and check
            if (mat[i][j] == word[0]){
                if (findMatch(mat, word, i, j, 0))
                    return true;
            }
        }
    }
    return false;
}

int main() {
    vector<vector<char>> mat = {{'T', 'E', 'E'}, {'S', 'G', 'K'}, {'T', 'E', 'L'}};
      	string word = "GEEK";	
    cout << (isWordExist(mat, word) ? "true" : "false");

    return 0;
}
Java 
class GFG {
    
    // Recursive Function to check if the word exists in the matrix or not
    static boolean findMatch(char[][] mat, String word, int x, int y, 
                             							  int wIdx) {
        int wLen = word.length();
        int n = mat.length;
        int m = mat[0].length;
        if (wIdx == wLen)
            return true;

        // Out of Boundary
        if (x < 0 || y < 0 || x >= n || y >= m)
            return false;

        // If grid matches with a letter while recursion
        if (mat[x][y] == word.charAt(wIdx)) {
            
            // Marking this cell as visited
            char temp = mat[x][y];
            mat[x][y] = '#';

            // finding subpattern in 4 directions
            boolean res = findMatch(mat, word, x - 1, y, wIdx + 1) ||
                          findMatch(mat, word, x + 1, y, wIdx + 1) ||
                          findMatch(mat, word, x, y - 1, wIdx + 1) ||
                          findMatch(mat, word, x, y + 1, wIdx + 1);
            mat[x][y] = temp;
            return res;
        }
        return false;
    }

    // Function to check if the word exists in the matrix or not
    static boolean isWordExist(char[][] mat, String word) {
        int wLen = word.length();
        int n = mat.length;
        int m = mat[0].length;

        // if total characters in matrix is less than word length
        if (wLen > n * m)
            return false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                
                // If first letter matches, then recur and check
                if (mat[i][j] == word.charAt(0)) {
                    if (findMatch(mat, word, i, j, 0))
                        return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        char[][] mat = {{'T', 'E', 'E'}, {'S', 'G', 'K'}, {'T', 'E', 'L'}};
        String word = "GEEK";
        System.out.println(isWordExist(mat, word));
    }
}
Python 
# Recursive Function to check if the word exists in the matrix or not
def findMatch(mat, word, x, y, wIdx):
    wLen = len(word)
    n = len(mat)
    m = len(mat[0])
    if wIdx == wLen:
        return True

    # Out of Boundary
    if x < 0 or y < 0 or x >= n or y >= m:
        return False

    # If grid matches with a letter while
    # recursion
    if mat[x][y] == word[wIdx]:

        # Marking this cell as visited
        temp = mat[x][y]
        mat[x][y] = '#'

        # finding subpattern in 4 directions
        res = (findMatch(mat, word, x - 1, y, wIdx + 1) or
               findMatch(mat, word, x + 1, y, wIdx + 1) or
               findMatch(mat, word, x, y - 1, wIdx + 1) or
               findMatch(mat, word, x, y + 1, wIdx + 1))

        mat[x][y] = temp
        return res

    return False

def isWordExist(mat, word):
    wLen = len(word)
    n = len(mat)
    m = len(mat[0])
  
    # if total characters in matrix is
    # less than word length
    if wLen > n * m:
        return False
        
    for i in range(n):
        for j in range(m):

            # If first letter matches, then recur and check
            if mat[i][j] == word[0]:
                if findMatch(mat, word, i, j, 0):
                    return True
    return False

if __name__ == "__main__":
    mat = [['T', 'E', 'E'], ['S', 'G', 'K'], ['T', 'E', 'L']]
    word = "GEEK"  
    print("true" if isWordExist(mat, word) else "false")
C# 
using System;

class GFG {
    
    // Recursive Function to check if the word exists in the matrix or not
    static bool findMatch(char[,] mat, string word, int x, int y, int wIdx) {
        int wLen = word.Length;
        int n = mat.GetLength(0);
        int m = mat.GetLength(1);

        if (wIdx == wLen)
            return true;

        // Out of Boundary
        if (x < 0 || y < 0 || x >= n || y >= m)
            return false;

        // If grid matches with a letter while
        // recursion
        if (mat[x, y] == word[wIdx]) {
            
            // Marking this cell as visited
            char temp = mat[x, y];
            mat[x, y] = '#';

            // finding subpattern in 4 directions
            bool res = findMatch(mat, word, x - 1, y, wIdx + 1) ||
                       findMatch(mat, word, x + 1, y, wIdx + 1) ||
                       findMatch(mat, word, x, y - 1, wIdx + 1) ||
                       findMatch(mat, word, x, y + 1, wIdx + 1);

            mat[x, y] = temp;
            return res;
        }
        return false;
    }

    // Function to check if the word exists in the matrix or not
    static bool isWordExist(char[,] mat, string word) {
        int wLen = word.Length;
        int n = mat.GetLength(0);
        int m = mat.GetLength(1);

        // if total characters in matrix is
        // less than word length
        if (wLen > n * m)
            return false;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
              
                // If first letter matches, then recur and check
                if (mat[i, j] == word[0]) {
                    if (findMatch(mat, word, i, j, 0))
                        return true;
                }
            }
        }
        return false;
    }

    static void Main() {
        char[,] mat = {{'T', 'E', 'E'}, {'S', 'G', 'K'}, {'T', 'E', 'L'}};
        string word = "GEEK";
        Console.WriteLine(isWordExist(mat, word) ? "true" : "false");
    }
}
JavaScript 
// Recursive Function to check if the word exists in the matrix or not
function findMatch(mat, word, x, y, wIdx) {
    const wLen = word.length;
    const n = mat.length;
    const m = mat[0].length;

    if (wIdx === wLen)
        return true;

    // Out of Boundary
    if (x < 0 || y < 0 || x >= n || y >= m)
        return false;

    // If grid matches with a letter while
    // recursion
    if (mat[x][y] === word[wIdx]) {
        // Marking this cell as visited
        const temp = mat[x][y];
        mat[x][y] = '#';

        // finding subpattern in 4 directions
        const res = findMatch(mat, word, x - 1, y, wIdx + 1) ||
                    findMatch(mat, word, x + 1, y, wIdx + 1) ||
                    findMatch(mat, word, x, y - 1, wIdx + 1) ||
                    findMatch(mat, word, x, y + 1, wIdx + 1);

        mat[x][y] = temp;
        return res;
    }


    return false;
}

// Function to check if the word exists in the matrix or not
function isWordExist(mat, word) {
    const wLen = word.length;
    const n = mat.length;
    const m = mat[0].length;

    // if total characters in matrix is
    // less than word length
    if (wLen > n * m)
        return false;

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            
            // If first letter matches, then recur and check
            if (mat[i][j] === word[0]) {
                if (findMatch(mat, word, i, j, 0))
                    return true;
            }
        }
    }
    return false;
}

// Driver Code
const mat = [['T', 'E', 'E'], ['S', 'G', 'K'], ['T', 'E', 'L']];
const word = "GEEK";
console.log(isWordExist(mat, word) ? "true" : "false");

Output
true

Time Complexity: O(n*m * 4k), where n × m is the matrix size and k is the word length
Auxiliary Space: O(k), due to recursion stack depth

Comment

Explore