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.
Problem statement taken from: https://leetcode.com/problems/word-search
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
Example 3:
Input: board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word = "ABCB"
Output: false
Constraints
- m == board.length
- n = board[i].length
- 1 <= m, n <= 6
- 1 <= word.length <= 15
- board and word consists of only lowercase and uppercase English letters.
Explanation
DFS algorithm
The movement across the m * n board is restricted to horizontal and vertical neighbors. So we can move only along four directions and not eight, since diagonal movement is restricted.
When we are pointing at a particular cell, we check if the word's 1st character matches the char in current cell. If yes, we match the next char of word in all the four directions of the current cell of grid. We continue doing this till we find the full word.
The way we navigate across the grid it resembles Depth First Search.
Let's check the algorithm:
// function main
- set x[4] = {1, -1, 0, 0}
y[4] = {0, 0, 1, -1}
- initialize i and j
- loop for i = 0; i < board.size(); i++
- loop for j = 0; j < board[0].size(); j++
- if dfs(board, i, j, 0, word)
- return true
// function dfs(board, i, j, position, word)
- if position >= word.size()
- return true
// call resolvable function to check the boundary conditions of grid
// and see if the char at word position matches the board index board[i][j]
- if resolvable(board, i, j, position, word)
- char t = board[i][j]
- board[i][j] = '.'
// if the current char matches we move across all the four directions to match the next char
- loop for k = 0; k < 4; k++
- if dfs(board, i + x[k], j + y[k], position + 1, word)
- return true
- board[i][j] = t
- return false
// function resolvable(board, i, j, position, word)
- return i >= 0 && i < board.size() && j >= 0 && j < board[0].size() && board[i][j] == word[position]
C++ solution
class Solution {
int x[4] = {1, -1, 0, 0};
int y[4] = {0, 0, 1, -1};
public:
bool resolvable(vector<vector<char>>& board, int i, int j, int position, string word){
return (i >= 0 && i < board.size() && j >= 0 && j < board[0].size() && board[i][j] == word[position]);
}
public:
bool dfs(vector<vector<char>>& board, int i, int j, int position, string word){
if(position >= word.size()){
return true;
}
if(resolvable(board, i, j, position, word)){
char t = board[i][j];
board[i][j] = '.';
for(int k = 0; k < 4; ++k){
if(dfs(board, i + x[k], j + y[k], position + 1, word)){
return true;
}
}
board[i][j] = t;
}
return false;
}
public:
bool exist(vector<vector<char>>& board, string word) {
int i, j;
for(i = 0; i < board.size(); i++){
for(j = 0; j < board[0].size(); j++){
if(dfs(board, i, j, 0, word)){
return true;
}
}
}
return false;
}
};
Golang solution
var x [4]int
var y [4]int
func resolvable(board [][]byte, i, j, position int, word string) bool {
return i >= 0 && i < len(board) && j >= 0 && j < len(board[0]) && word[position] == board[i][j]
}
func dfs(board [][]byte, i, j, position int, word string) bool {
if position >= len(word) {
return true
}
if resolvable(board, i, j, position, word) {
t := board[i][j]
board[i][j] = '.'
for k := 0; k < 4; k++ {
if dfs(board, i + x[k], j + y[k], position + 1, word) {
return true
}
}
board[i][j] = t
}
return false
}
func exist(board [][]byte, word string) bool {
x = [...]int{1, -1, 0, 0}
y = [...]int{0, 0 , 1, -1}
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[0]); j++ {
if dfs(board, i, j, 0, word) {
return true
}
}
}
return false
}
Javascript solution
var x = [1, -1, 0, 0];
var y = [0, 0, 1, -1];
function resolvable(board, i, j, position, word){
return i >= 0 && i < board.length && j >= 0 && j < board[0].length && word[position] == board[i][j]
}
function dfs(board, i, j, position, word){
if(position >= word.length) {
return true;
}
if(resolvable(board, i, j, position, word)) {
var t = board[i][j];
board[i][j] = '.';
for(var k = 0 ; k < 4; k++){
if(dfs(board, i + x[k], j + y[k], position + 1, word)){
return true;
}
}
board[i][j] = t;
}
return false;
}
var exist = function(board, word) {
for(var i = 0; i < board.length; i++){
for(var j = 0; j < board[0].length; j++){
if(dfs(board, i, j, 0, word)) {
return true;
}
}
}
return false;
}
Let's dry-run our algorithm to see how the solution works.
Input: board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]]
word = "SEE"
Step 1: initialize i, j
Step 2: loop for i = 0; i < board.size()
0 < 3
true
loop for j = 0; j < board[0].size()
0 < 4
true
dfs(board, i, j, 0, word)
dfs(board, 0, 0, 0, word)
Step 3: //in function dfs
if position >= word.size()
0 >= 3
false
if resolvable(board, i, j, position, word)
- i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
- 0 >= 0 && 0 < 3 && j >= 0 && 0 < 4 && word[0] == board[0][0]
- true && 'S' == 'A'
- false
return false
Step 4: We reach at step 2 and increment j
i = 0
j = 1
dfs(board, i, j, 0, word)
dfs(board, 0, 1, 0, word)
Step 5: //in function dfs
if position >= word.size()
0 >= 3
false
if resolvable(board, i, j, position, word)
- i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
- 0 >= 0 && 0 < 3 && 1 >= 0 && 1 < 4 && word[0] == board[0][1]
- true && 'S' == 'B'
- false
return false
Step 6: We reach at step 2 and increment j
i = 0
j = 2
dfs(board, i, j, 0, word)
dfs(board, 0, 2, 0, word)
Step 7: //in function dfs
if position >= word.size()
0 >= 3
false
if resolvable(board, i, j, position, word)
- i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
- 0 >= 0 && 0 < 3 && 2 >= 0 && 2 < 4 && word[0] == board[0][2]
- true && 'S' == 'C'
- false
return false
Step 8: We reach at step 2 and increment j
i = 0
j = 3
dfs(board, i, j, 0, word)
dfs(board, 0, 3, 0, word)
Step 9: //in function dfs
if position >= word.size()
0 >= 3
false
if resolvable(board, i, j, position, word)
- i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
- 0 >= 0 && 0 < 3 && 3 >= 0 && 3 < 4 && word[0] == board[0][3]
- true && 'S' == 'E'
- false
return false
Step 10: We reach at step 2 and increment j
i = 0
j = 4
dfs(board, i, j, 0, word)
dfs(board, 0, 3, 0, word)
Step 11: //in function dfs
if position >= word.size()
0 >= 3
false
if resolvable(board, i, j, position, word)
- i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
- 0 >= 0 && 0 < 3 && 3 >= 0 && 4 < 4 && word[0] == board[0][3]
- false && 'S' == 'E'
- false
return false
Step 12: We reach at step 2 and increment i and j is 0
i = 1
j = 0
dfs(board, i, j, 0, word)
dfs(board, 1, 0, 0, word)
Step 13: //in function dfs
if position >= word.size()
0 >= 3
false
if resolvable(board, i, j, position, word)
- i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
- 1 >= 0 && 1 < 3 && 0 >= 0 && 0 < 4 && word[0] == board[1][0]
- true && 'S' == 'S'
- true
- t = board[i][j]
- t = 'S'
- board[i][j] = '.'
- board[1][0] = '.'
loop for k = 0; k < 4
- dfs(board, i + x[k], j + y[k], position + 1, word)
- dfs(board, 1 + x[0], 0 + y[0], 0 + 1, word)
- dfs(board, 1 + 1, 0 + 0, 0 + 1, word)
- dfs(board, 2, 0 + 0, 1, word)
// recursive call to dfs function
if position >= word.size()
1 >= 3
false
if resolvable(board, i, j, position, word)
- i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
- 2 >= 0 && 2 < 3 && 0 >= 0 && 0 < 4 && word[1] == board[2][0]
- true && 'E' == 'A'
- false
k++
k = 1
loop for k < 4
- dfs(board, i + x[k], j + y[k], position + 1, word)
- dfs(board, 1 + x[1], 0 + y[1], 0 + 1, word)
- dfs(board, 1 - 1, 0 + 0, 0 + 1, word)
- dfs(board, 0, 0, 1, word)
// recursive call to dfs function
if position >= word.size()
1 >= 3
false
if resolvable(board, i, j, position, word)
- i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
- 0 >= 0 && 0 < 3 && 0 >= 0 && 0 < 4 && word[1] == board[0][0]
- true && 'E' == 'A'
- false
k++
k = 2
loop for k < 4
- dfs(board, i + x[k], j + y[k], position + 1, word)
- dfs(board, 1 + x[2], 0 + y[2], 0 + 1, word)
- dfs(board, 1 + 0, 0 + 1, 0 + 1, word)
- dfs(board, 1, 1, 1, word)
// recursive call to dfs function
if position >= word.size()
1 >= 3
false
if resolvable(board, i, j, position, word)
- i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
- 1 >= 0 && 1 < 3 && 1 >= 0 && 1 < 4 && word[1] == board[1][1]
- true && 'E' == 'F'
- false
k++
k = 3
loop for k < 4
- dfs(board, i + x[k], j + y[k], position + 1, word)
- dfs(board, 1 + x[3], 0 + y[3], 0 + 1, word)
- dfs(board, 1 + 0, 0 - 1, 0 + 1, word)
- dfs(board, 1, -1, 1, word)
// recursive call to dfs function
if position >= word.size()
1 >= 3
false
if resolvable(board, i, j, position, word)
- i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
- 1 >= 0 && 1 < 3 && -1 >= 0 && 1 < 4 && word[1] == board[1][1]
- false
k++
k = 4
loop for k < 4
- false
return false
Step 14: We reach at step 2 and increment i and j is 0
i = 1
j = 1
dfs(board, i, j, 0, word)
dfs(board, 1, 1, 0, word)
This is false since word[0] != board[1][1]
'S' != 'F'
Step 15: We reach at step 2 and increment i and j is 1
i = 1
j = 2
dfs(board, i, j, 0, word)
dfs(board, 1, 2, 0, word)
This is false since word[0] != board[1][2]
'S' != 'C'
Step 16: We reach at step 2 and increment i and j is 2
i = 1
j = 3
dfs(board, i, j, 0, word)
dfs(board, 1, 3, 0, word)
Step 17: //in function dfs
if position >= word.size()
0 >= 3
false
if resolvable(board, i, j, position, word)
- i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
- 1 >= 0 && 1 < 3 && 3 >= 0 && 3 < 4 && word[0] == board[1][3]
- true && 'S' == 'S'
- true
- t = board[i][j]
- t = 'S'
- board[i][j] = '.'
- board[1][3] = '.'
loop for k = 0; k < 4
- dfs(board, i + x[k], j + y[k], position + 1, word)
- dfs(board, 1 + x[0], 3 + y[0], 0 + 1, word)
- dfs(board, 1 + 1, 3 + 0, 0 + 1, word)
- dfs(board, 2, 3, 1, word)
// recursive call to dfs function
if position >= word.size()
1 >= 3
false
if resolvable(board, i, j, position, word)
- i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
- 2 >= 0 && 2 < 3 && 3 >= 0 && 3 < 4 && word[1] == board[2][3]
- true && 'E' == 'E'
- true
- t = board[i][j]
- t = 'E'
- board[i][j] = '.'
- board[2][3] = '.'
loop for k = 0; k < 4
- dfs(board, i + x[k], j + y[k], position + 1, word)
- dfs(board, 2 + x[0], 3 + y[0], 1 + 1, word)
- dfs(board, 2 + 1, 3 + 0, 2, word)
- dfs(board, 3, 3, 1, word)
// recursive call to dfs function
if position >= word.size()
2 >= 3
false
if resolvable(board, i, j, position, word)
- i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
- 3 >= 0 && 3 < 3 && 3 >= 0 && 3 < 4 && word[2] == board[2][3]
- false && 'E' == 'E'
- false
k++
k = 1
loop for k = 0; k < 4
- dfs(board, i + x[k], j + y[k], position + 1, word)
- dfs(board, 2 + x[1], 3 + y[1], 1 + 1, word)
- dfs(board, 2 - 1, 3 + 0, 2, word)
- dfs(board, 1, 3, 2, word)
// recursive call to dfs function
if position >= word.size()
2 >= 3
false
if resolvable(board, i, j, position, word)
- i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
- 1 >= 0 && 1 < 3 && 3 >= 0 && 3 < 4 && word[2] == board[1][3]
- false && 'E' == 'C'
- false
k++
k = 2
loop for k = 0; k < 4
- dfs(board, i + x[k], j + y[k], position + 1, word)
- dfs(board, 2 + x[2], 3 + y[2], 1 + 1, word)
- dfs(board, 2 + 0, 3 + 1, 2, word)
- dfs(board, 2, 4, 2, word)
// recursive call to dfs function
if position >= word.size()
2 >= 3
false
if resolvable(board, i, j, position, word)
- i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
- 2 >= 0 && 2 < 3 && 4 >= 0 && 4 < 4 && word[2] == board[2][4]
- false
k++
k = 3
loop for k = 0; k < 4
- dfs(board, i + x[k], j + y[k], position + 1, word)
- dfs(board, 2 + x[3], 3 + y[3], 1 + 1, word)
- dfs(board, 2 + 0, 3 - 1, 2, word)
- dfs(board, 2, 2, 2, word)
// recursive call to dfs function
if position >= word.size()
2 >= 3
false
if resolvable(board, i, j, position, word)
- i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
- 2 >= 0 && 2 < 3 && 2 >= 0 && 2 < 4 && word[2] == board[2][2]
- true && 'E' == 'E'
- true
- t = board[i][j]
- t = 'E'
- board[i][j] = '.'
- board[2][2] = '.'
loop for k = 0; k < 4
- dfs(board, i + x[k], j + y[k], position + 1, word)
- dfs(board, 2 + x[0], 2 + y[0], 2 + 1, word)
- dfs(board, 2 + 1, 2 + 0, 3, word)
- dfs(board, 2, 2, 3, word)
// recursive call to dfs function
if position >= word.size()
3 >= 3
true
Step 18: // Here we have covered all chars of the string "SEE" and found in the grid.
// So we return true from this recursive calls and return to exist function.
So the answer we return is true.
Top comments (0)