Problem

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

Example 1:

$$ \begin{bmatrix} \colorbox{YellowOrange} A & \colorbox{YellowOrange} B & \colorbox{YellowOrange} C & E \\ S & F & \colorbox{YellowOrange} C & S \\ A & \colorbox{YellowOrange} D & \colorbox{YellowOrange} E & E \end{bmatrix} $$

1
2
3
4
5
6
7
8

Input: 
board = [
	["A","B","C","E"],
	["S","F","C","S"],
	["A","D","E","E"]
], word = "ABCCED"

Output: true

Example 2: $$ \begin{bmatrix} A & B & C & E \\ S & F & C & \colorbox{YellowOrange} S \\ A & D & \colorbox{YellowOrange} E & \colorbox{YellowOrange} E \end{bmatrix} $$

1
2
3
4
5
6
7

Input: 
board = [
	["A","B","C","E"],
	["S","F","C","S"],
	["A","D","E","E"]
], word = "SEE"
Output: true

Example 3: $$ \begin{bmatrix} A & B & C & E \\ S & F & C & S \\ A & D & E & E \end{bmatrix} $$

1
2
3
4
5
6
7

Input: 
board = [
	["A","B","C","E"],
	["S","F","C","S"],
	["A","D","E","E"]
], word = "ABCB"
Output: false

Follow up

Word Search 2 - Return All Words

Solution

This problem can be solve by using a typical DFS method and backtracking.

We need to make sure that we don’t visit the same character again, if it is already used in word search. We can either use hashSet or we can modify the board temporarily. We will use some char like # OR * whenever we use some char in board, and revert after checking and backtrack.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

public boolean exist(char[][] board, String word) {
	int m = board.length;
	int n = board[0].length;

	for (int i = 0; i<m; i++) {
		for (int j = 0; j<n; j++) {
			if (dfs(board, word, i, j, 0)) {
				return true;
			}
		}
	}

	return false;
}

public boolean dfs(char[][] board, String word, int r, int c, int idx) {

	// base case 1
	if (idx == word.length()) {
		return true;
	}
	int m = board.length;
	int n = board[0].length;
	// base case 1
	if (r<0 || c<0 || r >= m || c >= n) {
		return false;
	}
	// base case 3
	if(board[r][c] != word.charAT(idx)){
		return false;
	}


	
	char temp = board[i][j];
	board[r][c] = '#';
	
	boolean ans = dfs(board, word, r - 1, c, idx + 1) ||
		dfs(board, word, r + 1, c, idx + 1) ||
		dfs(board, word, r, c - 1, idx + 1) ||
		dfs(board, word, r, c + 1, idx + 1);
	
	board[r][c] = temp;
	

	return ans;
}

Time complexity = O(n*m* 4^len(word)) = O(4^n)