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
Table of Contents
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 Complexity | Space Complexity | |
C++ | O(m * n * 4L) | O(L) |
Java | O(m * n * 4L) | O(L) |
JavaScript | O(m * n * 4L) | O(L) |
Python | O(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 additionalvisited
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.