Word Search LeetCode Solution

Last updated on January 19th, 2025 at 10:47 pm

Here, we see a Word Search LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array, Backtracking

Companies

Bloomberg, Facebook, Microsoft

Level of Question

Medium

Word Search LeetCode Solution

Word Search LeetCode Solution

1. 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

2. Coding Pattern Used in Solution

The coding pattern used in the provided code is “Islands”. This pattern is commonly used to solve problems that involve traversing a grid (2D matrix) to find connected components or paths. The code uses Depth First Search (DFS) to explore all possible paths in the grid to match the given word.

3. Code Implementation in Different Languages

3.1 Word Search 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;
    }
};

3.2 Word Search 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.3 Word Search 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;    
};

3.4 Word Search 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       

4. Time and Space Complexity

Time ComplexitySpace Complexity
C++O(m * n * 4L)O(L)
JavaO(m * n * 4L)O(L)
JavaScriptO(m * n * 4L)O(L)
PythonO(m * n * 4L)O(L + m * n)

where m is the number of rows and n is the number of columns. L is the length of the word.

  • The time complexity is exponential due to the recursive DFS exploring all possible paths.
  • The space complexity is primarily determined by the depth of the recursive stack (L) and, in Python, the additional visited dictionary.
  • The algorithm is efficient for small grids and short words but may become computationally expensive for larger inputs due to the exponential growth of DFS calls.
Scroll to Top