Coding Practice: Word Search

Coding Practice: Word Search

January 5, 2023

Moch Lutfi
Name
Moch Lutfi
Twitter
@kaptenupi

Problem

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:


board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

Solution

Given a two-dimensional grid and a word to find out whether the word exists in the grid. Words must be composed of letters in adjacent cells in the order of letters. Among them, the "adjacent" cells are those adjacent or vertical cells.The letters in the same cell are not allowed to be reused.

Start at any starting point on the map, searches in DFS in 4 directions, and output true until all the words of the words are found, otherwise the output False.

Step 1

Define a function exist(board [][]byte, word string) bool. This function will take in a 2D grid of characters board and a string word, and return a boolean indicating whether the word exists in the board.

solution.go

func exist(board [][]byte, word string) bool {
return false
}

Step 2

Create a helper function dfs(board [][]byte, word string, i, j int) bool that will be used to perform the DFS. This function will take in the same board and word, as well as the current indices i and j that represent the position in the board where the DFS is currently at. The function will return a boolean indicating whether the word can be formed by following a path in the board starting from position (i, j).

solution.go

func exist(board [][]byte, word string) bool {
// define the dfs function
var dfs func(board [][]byte, word string, i, j int) bool
dfs = func(board [][]byte, word string, i, j int) bool {
// check if the current character in the board matches the first character in the word
if board[i][j] != word[0] {
return false
}
// check if the word has only one character
if len(word) == 1 {
return true
}
board[i][j] = '#'
// check all the neighboring cells to see if the word can be formed by extending the path from the current position
// go left i-1
if i > 0 && dfs(board, word[1:], i-1, j) {
return true
}
// go right i+1
if i < len(board)-1 && dfs(board, word[1:], i+1, j) {
return true
}
// go up j-1
if j > 0 && dfs(board, word[1:], i, j-1) {
return true
}
// go down j+1
if j < len(board[0])-1 && dfs(board, word[1:], i, j+1) {
return true
}
// reset the current position back to its original value
board[i][j] = word[0]
return false
}
// iterate through all the cells in the board and use the dfs function to check if the word can be formed starting from each cell
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[0]); j++ {
if dfs(board, word, i, j) {
return true
}
}
}
return false
}

Step 3

In the dfs function, check if the current character in the board at position (i, j) is equal to the first character in the word. If it is not, return false as it means that the word cannot be formed starting from this position.

solution.go

func exist(board [][]byte, word string) bool {
// define the dfs function
var dfs func(board [][]byte, word string, i, j int) bool
dfs = func(board [][]byte, word string, i, j int) bool {
// check if the current character in the board matches the first character in the word
if board[i][j] != word[0] {
return false
}
// check if the word has only one character
if len(word) == 1 {
return true
}
board[i][j] = '#'
// check all the neighboring cells to see if the word can be formed by extending the path from the current position
// go left i-1
if i > 0 && dfs(board, word[1:], i-1, j) {
return true
}
// go right i+1
if i < len(board)-1 && dfs(board, word[1:], i+1, j) {
return true
}
// go up j-1
if j > 0 && dfs(board, word[1:], i, j-1) {
return true
}
// go down j+1
if j < len(board[0])-1 && dfs(board, word[1:], i, j+1) {
return true
}
// reset the current position back to its original value
board[i][j] = word[0]
return false
}
// iterate through all the cells in the board and use the dfs function to check if the word can be formed starting from each cell
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[0]); j++ {
if dfs(board, word, i, j) {
return true
}
}
}
return false
}

Step 4

If the current character in the board matches the first character in the word, check if the word has only one character. If it does, return true as the word has been found.

solution.go

func exist(board [][]byte, word string) bool {
// define the dfs function
var dfs func(board [][]byte, word string, i, j int) bool
dfs = func(board [][]byte, word string, i, j int) bool {
// check if the current character in the board matches the first character in the word
if board[i][j] != word[0] {
return false
}
// check if the word has only one character
if len(word) == 1 {
return true
}
board[i][j] = '#'
// check all the neighboring cells to see if the word can be formed by extending the path from the current position
// go left i-1
if i > 0 && dfs(board, word[1:], i-1, j) {
return true
}
// go right i+1
if i < len(board)-1 && dfs(board, word[1:], i+1, j) {
return true
}
// go up j-1
if j > 0 && dfs(board, word[1:], i, j-1) {
return true
}
// go down j+1
if j < len(board[0])-1 && dfs(board, word[1:], i, j+1) {
return true
}
// reset the current position back to its original value
board[i][j] = word[0]
return false
}
// iterate through all the cells in the board and use the dfs function to check if the word can be formed starting from each cell
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[0]); j++ {
if dfs(board, word, i, j) {
return true
}
}
}
return false
}

Step 5

If the word has more than one character, mark the current position in the board as visited by setting it to a special character such as '#'.

solution.go

func exist(board [][]byte, word string) bool {
// define the dfs function
var dfs func(board [][]byte, word string, i, j int) bool
dfs = func(board [][]byte, word string, i, j int) bool {
// check if the current character in the board matches the first character in the word
if board[i][j] != word[0] {
return false
}
// check if the word has only one character
if len(word) == 1 {
return true
}
board[i][j] = '#'
// check all the neighboring cells to see if the word can be formed by extending the path from the current position
// go left i-1
if i > 0 && dfs(board, word[1:], i-1, j) {
return true
}
// go right i+1
if i < len(board)-1 && dfs(board, word[1:], i+1, j) {
return true
}
// go up j-1
if j > 0 && dfs(board, word[1:], i, j-1) {
return true
}
// go down j+1
if j < len(board[0])-1 && dfs(board, word[1:], i, j+1) {
return true
}
// reset the current position back to its original value
board[i][j] = word[0]
return false
}
// iterate through all the cells in the board and use the dfs function to check if the word can be formed starting from each cell
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[0]); j++ {
if dfs(board, word, i, j) {
return true
}
}
}
return false
}

Step 6

Check all the neighboring cells (horizontally and vertically) of the current position (i, j) to see if the word can be formed by extending the path from the current position. If the word can be formed by extending the path from any of the neighboring cells, return true.

solution.go

func exist(board [][]byte, word string) bool {
// define the dfs function
var dfs func(board [][]byte, word string, i, j int) bool
dfs = func(board [][]byte, word string, i, j int) bool {
// check if the current character in the board matches the first character in the word
if board[i][j] != word[0] {
return false
}
// check if the word has only one character
if len(word) == 1 {
return true
}
board[i][j] = '#'
// check all the neighboring cells to see if the word can be formed by extending the path from the current position
// go left i-1
if i > 0 && dfs(board, word[1:], i-1, j) {
return true
}
// go right i+1
if i < len(board)-1 && dfs(board, word[1:], i+1, j) {
return true
}
// go up j-1
if j > 0 && dfs(board, word[1:], i, j-1) {
return true
}
// go down j+1
if j < len(board[0])-1 && dfs(board, word[1:], i, j+1) {
return true
}
// reset the current position back to its original value
board[i][j] = word[0]
return false
}
// iterate through all the cells in the board and use the dfs function to check if the word can be formed starting from each cell
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[0]); j++ {
if dfs(board, word, i, j) {
return true
}
}
}
return false
}

Step 7

If the word cannot be formed by extending the path from any of the neighboring cells, reset the current position in the board back to its original value and return false.

solution.go

func exist(board [][]byte, word string) bool {
// define the dfs function
var dfs func(board [][]byte, word string, i, j int) bool
dfs = func(board [][]byte, word string, i, j int) bool {
// check if the current character in the board matches the first character in the word
if board[i][j] != word[0] {
return false
}
// check if the word has only one character
if len(word) == 1 {
return true
}
board[i][j] = '#'
// check all the neighboring cells to see if the word can be formed by extending the path from the current position
// go left i-1
if i > 0 && dfs(board, word[1:], i-1, j) {
return true
}
// go right i+1
if i < len(board)-1 && dfs(board, word[1:], i+1, j) {
return true
}
// go up j-1
if j > 0 && dfs(board, word[1:], i, j-1) {
return true
}
// go down j+1
if j < len(board[0])-1 && dfs(board, word[1:], i, j+1) {
return true
}
// reset the current position back to its original value
board[i][j] = word[0]
return false
}
// iterate through all the cells in the board and use the dfs function to check if the word can be formed starting from each cell
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[0]); j++ {
if dfs(board, word, i, j) {
return true
}
}
}
return false
}

Step 8

In the exist function, iterate through all the cells in the board and use the dfs function to check if the word can be formed starting from each cell. If the word can be formed starting from any cell, return true.

Return false if the word cannot be formed starting from any cell.

solution.go

func exist(board [][]byte, word string) bool {
// define the dfs function
var dfs func(board [][]byte, word string, i, j int) bool
dfs = func(board [][]byte, word string, i, j int) bool {
// check if the current character in the board matches the first character in the word
if board[i][j] != word[0] {
return false
}
// check if the word has only one character
if len(word) == 1 {
return true
}
board[i][j] = '#'
// check all the neighboring cells to see if the word can be formed by extending the path from the current position
// go left i-1
if i > 0 && dfs(board, word[1:], i-1, j) {
return true
}
// go right i+1
if i < len(board)-1 && dfs(board, word[1:], i+1, j) {
return true
}
// go up j-1
if j > 0 && dfs(board, word[1:], i, j-1) {
return true
}
// go down j+1
if j < len(board[0])-1 && dfs(board, word[1:], i, j+1) {
return true
}
// reset the current position back to its original value
board[i][j] = word[0]
return false
}
// iterate through all the cells in the board and use the dfs function to check if the word can be formed starting from each cell
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[0]); j++ {
if dfs(board, word, i, j) {
return true
}
}
}
return false
}

Step 1

Define a function exist(board [][]byte, word string) bool. This function will take in a 2D grid of characters board and a string word, and return a boolean indicating whether the word exists in the board.

Step 2

Create a helper function dfs(board [][]byte, word string, i, j int) bool that will be used to perform the DFS. This function will take in the same board and word, as well as the current indices i and j that represent the position in the board where the DFS is currently at. The function will return a boolean indicating whether the word can be formed by following a path in the board starting from position (i, j).

Step 3

In the dfs function, check if the current character in the board at position (i, j) is equal to the first character in the word. If it is not, return false as it means that the word cannot be formed starting from this position.

Step 4

If the current character in the board matches the first character in the word, check if the word has only one character. If it does, return true as the word has been found.

Step 5

If the word has more than one character, mark the current position in the board as visited by setting it to a special character such as '#'.

Step 6

Check all the neighboring cells (horizontally and vertically) of the current position (i, j) to see if the word can be formed by extending the path from the current position. If the word can be formed by extending the path from any of the neighboring cells, return true.

Step 7

If the word cannot be formed by extending the path from any of the neighboring cells, reset the current position in the board back to its original value and return false.

Step 8

In the exist function, iterate through all the cells in the board and use the dfs function to check if the word can be formed starting from each cell. If the word can be formed starting from any cell, return true.

Return false if the word cannot be formed starting from any cell.

solution.go
ExpandClose

func exist(board [][]byte, word string) bool {
return false
}

Dry Run

Let's try dry run using example below:


board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
Given word = "ABCCED", return true.

ijwordboard[i][j]word[0]return
00ABCCEDAA
10BCCEDSBfalse
01BCCEDBB
11CCEDFCfalse
00CCED#Cfalse
02CCEDCC
12CEDCC
02ED#Efalse
22EDEE
12D#Dfalse
21DDDtrue