Last updated on October 9th, 2024 at 10:44 pm

Here, We see Word Search LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Word Search LeetCode Solution

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

1. Word Search Leetcode Solution C++

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if(board.size() == 0) return false;
        bool found = false;
        int m = board.size(), n = board[0].size();
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++){
                if(board[i][j] == word[0]) backtrack(board, 1, i, j, m, n, word, found);
                if(found) return true;
            }
        return false;
    }
    
    void backtrack(vector<vector<char>>& board, int pos, int r, int c, int m, int n, string& word, bool& found){
        if(board[r][c] == '0' || found) return;
        if(pos == word.size()){
            found = true;
            return;
        }
        char tmp = board[r][c];
        board[r][c] = '0';
        if(r - 1 >= 0 && board[r - 1][c] == word[pos]) backtrack(board, pos + 1, r - 1, c, m, n, word, found);
        if(r + 1 < m  && board[r + 1][c] == word[pos]) backtrack(board, pos + 1, r + 1, c, m, n, word, found);
        if(c + 1 < n  && board[r][c + 1] == word[pos]) backtrack(board, pos + 1, r, c + 1, m, n, word, found);
        if(c - 1 >= 0 && board[r][c - 1] == word[pos]) backtrack(board, pos + 1, r, c - 1, m, n, word, found);
        board[r][c] = tmp;
    }
};

2. Word Search Leetcode Solution Java

class Solution {
    public boolean exist(char[][] board, String word) {
        for(int r=0; r<board.length; r++)
            for(int c=0; c<board[0].length; c++)
                if(board[r][c]==word.charAt(0) && help(board,word,0,r,c))
                    return true;
        
        return false;
    }
    
    public boolean help(char[][] b, String word, int start, int r, int c){
        if(word.length() <= start)
            return true;
       
        if(r<0 ||c<0 || r>=b.length || c>=b[0].length || b[r][c]=='0' || b[r][c]!=word.charAt(start))
            return false;

        char tmp = b[r][c];
        b[r][c] = '0';
        
        if(help(b,word,start+1,r+1,c) ||
          help(b,word,start+1,r-1,c) ||
          help(b,word,start+1,r,c+1) ||
          help(b,word,start+1,r,c-1))
            return true;
        
        b[r][c] = tmp;
        
        return false;
    }
}

3. Word Search Leetcode Solution JavaScript

var exist = function(board, word) {
    let dfs = (board, i, j, word, count=0) => {
        if(count===word.length) return true;
        if(i<0 || i>=board.length || j<0 || j>=board[0].length || board[i][j]!==word[count]) return false;
        let temp = board[i][j];
        board[i][j] = '';
        let 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;
    }
    
    for(let i = 0; i<board.length; i++){
        for(let j = 0; j<board[0].length; j++){
            if(board[i][j]===word[0] && dfs(board, i, j, word)){
                return true;
            }
        }
    }
    return false;    
};

4. Word Search Leetcode Solution Python

class Solution(object):
    def exist(self, board, word):
        visited = {}

        for i in range(len(board)):
            for j in range(len(board[0])):
                if self.getWords(board, word, i, j, visited):
                    return True
        
        return False

    def getWords(self, board, word, i, j, visited, pos = 0):
        if pos == len(word):
            return True

        if i < 0 or i == len(board) or j < 0 or j == len(board[0]) or visited.get((i, j)) or word[pos] != board[i][j]:
            return False

        visited[(i, j)] = True
        res = self.getWords(board, word, i, j + 1, visited, pos + 1) \
                or self.getWords(board, word, i, j - 1, visited, pos + 1) \
                or self.getWords(board, word, i + 1, j, visited, pos + 1) \
                or self.getWords(board, word, i - 1, j, visited, pos + 1)
        visited[(i, j)] = False

        return res