Leetcode 79. Word Search
Problem Explanation
We are given a 2D grid of characters and a string word. We need to determine if the word exists in the grid. A word is valid if consecutive characters of the word exist in sequential, either horizontally or vertically.
For example, let's take a look at this board:
1 2 3[ 4 ['A','B','C','E'], 5 ['S','F','C','S'], 6 ['A','D','E','E'] 7]
The word "ABCCED" exists in the board since we can traverse from 'A'->'B'->'C'->'C'->'E'->'D'.
The word "SEE" also exists since we can traverse from 'S'->'E'->'E'.
The word "ABCB" does not exist in the board because 'B' cannot be reached from 'C' in the last traversal.
Solution Approach
The strategy we will use to solve this problem is depth-first search (DFS). DFS is a searching algorithm that explores as far as possible along each branch before backtracking. For our problem, we will start from each cell in the 2D grid and check if the current cell character matches the first character of the word. If it matches, we use DFS to explore all of its neighbors (up, down, left, right), moving to the next character in the word. To avoid visiting a cell twice, we temporarily mark it as visited during the DFS using some character that doesn't exist in the grid(like "*"). If we find the whole word, we return true. If the word does not exist, we backtrack, unmark the cell, and continue to the next cell.
Solution in Python
1 2Python 3class Solution: 4 def exist(self, board, word): 5 if not board: 6 return False 7 for i in range(len(board)): 8 for j in range(len(board[0])): 9 if self.dfs(board, i, j, word): 10 # If the word exists, return True 11 return True 12 # If the word doesn't exist in the grid, return False 13 return False 14 15 def dfs(self, board, i, j, word): 16 # If we have found the word 17 if len(word) == 0: 18 return True 19 if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or word[0] != board[i][j]: 20 return False 21 tmp = board[i][j] 22 board[i][j] = "#" 23 # Find the word in the neighbors 24 res = self.dfs(board, i+1, j, word[1:]) or self.dfs(board, i-1, j, word[1:]) \ 25 or self.dfs(board, i, j+1, word[1:]) or self.dfs(board, i, j-1, word[1:]) 26 board[i][j] = tmp 27 return res
Solution in Java
1
2Java
3public class Solution {
4 public boolean exist(char[][] board, String word) {
5 if (board.length == 0) {
6 return false;
7 }
8 for (int i = 0; i < board.length; i++) {
9 for (int j = 0; j < board[0].length; j++) {
10 if (dfs(board, i, j, word, 0)) {
11 // If the word exists, return true
12 return true;
13 }
14 }
15 }
16 // If the word does not exist, return false
17 return false;
18 }
19
20 private boolean dfs(char[][] board, int i, int j, String word, int k) {
21 if (i < 0 || j < 0 || i == board.length || j == board[0].length || board[i][j] != word.charAt(k)) {
22 return false;
23 }
24 if (k == word.length() - 1) {
25 return true;
26 }
27 char temp = board[i][j];
28 board[i][j] = '/';
29 boolean res = dfs(board, i+1, j, word, k+1) || dfs(board, i-1, j, word, k+1) ||
30 dfs(board, i, j+1, word, k+1) || dfs(board, i, j-1, word, k+1);
31 board[i][j] = temp;
32 return res;
33 }
34}
In both Python and Java solutions, the algorithm iterates over every cell in the input grid and runs a Depth-First Search to determine if a valid word exists from that particular cell. This approach ensures that all possible words starting from each cell are checked. The runtime complexity of this solution is O(N * 4^L) where N is the number of cells in the grid and L is the length of the word to be matched.## Solution in JavaScript
In the following JavaScript solution, we use the same strategy of DFS to search for the word in the grid. Here is the code snippet for the solution:
1
2JavaScript
3var exist = function(board, word) {
4 for (let i = 0; i < board.length; i++) {
5 for (let j = 0; j < board[0].length; j++) {
6 if (dfs(board, word, i, j, 0)) {
7 // If the word exist, return true
8 return true;
9 }
10 }
11 }
12 // If the word doesn't exist in the grid, return false
13 return false;
14};
15
16var dfs = function(board, word, row, col, index) {
17 if (index == word.length) {
18 return true;
19 }
20 if (row < 0 || col < 0 || row >= board.length || col >= board[0].length || board[row][col] !== word[index]) {
21 return false;
22 }
23
24 let temp = board[row][col];
25 board[row][col] = '-';
26 let exists = dfs(board, word, row+1, col, index+1) || dfs(board, word, row-1, col, index+1) ||
27 dfs(board, word, row, col+1, index+1) || dfs(board, word, row, col-1, index+1);
28 board[row][col] = temp;
29 return exists;
30};
JavaScript solution mimics the Python and Java solution strategy. It defines a helper function for DFS (dfs) and calls it for each cell in the grid. This solution will traverse in four directions(left, right, up, down) and uses index to match the word character in DFS. If match found it will keep on traversing for the next character else it will return false back to the main function which will start traversing from the next index. The same process continues until all cells in the grid are traversed and word is matched or not.
The JavaScript solution also has a time complexity of O(N * 4^L), where N is the number of cells in the grid and L is the length of the word, for the same reasons as the Python and Java solutions.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.