Published on

# Coding Practice: Word Search

Authors
• Name
Moch Lutfi
@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:

`_10board =_10[_10 ['A','B','C','E'],_10 ['S','F','C','S'],_10 ['A','D','E','E']_10]_10_10Given word = "ABCCED", return true._10Given word = "SEE", return true._10Given 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
`_4_4func exist(board [][]byte, word string) bool {_4 return false_4}`

## 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
`_45func exist(board [][]byte, word string) bool {_45 // define the dfs function_45 var dfs func(board [][]byte, word string, i, j int) bool_45 dfs = func(board [][]byte, word string, i, j int) bool {_45 // check if the current character in the board matches the first character in the word_45 if board[i][j] != word {_45 return false_45 }_45 // check if the word has only one character_45 if len(word) == 1 {_45 return true_45 }_45 board[i][j] = '#'_45 // check all the neighboring cells to see if the word can be formed by extending the path from the current position_45 // go left i-1_45 if i > 0 && dfs(board, word[1:], i-1, j) {_45 return true_45 }_45 // go right i+1_45 if i < len(board)-1 && dfs(board, word[1:], i+1, j) {_45 return true_45 }_45 // go up j-1_45 if j > 0 && dfs(board, word[1:], i, j-1) {_45 return true_45 }_45 // go down j+1_45 if j < len(board)-1 && dfs(board, word[1:], i, j+1) {_45 return true_45 }_45 // reset the current position back to its original value_45 board[i][j] = word_45 return false_45 }_45_45 // 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_45 for i := 0; i < len(board); i++ {_45 for j := 0; j < len(board); j++ {_45 if dfs(board, word, i, j) {_45 return true_45 }_45 }_45 }_45 return false_45}`

## 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
`_45func exist(board [][]byte, word string) bool {_45 // define the dfs function_45 var dfs func(board [][]byte, word string, i, j int) bool_45 dfs = func(board [][]byte, word string, i, j int) bool {_45 // check if the current character in the board matches the first character in the word_45 if board[i][j] != word {_45 return false_45 }_45 // check if the word has only one character_45 if len(word) == 1 {_45 return true_45 }_45 board[i][j] = '#'_45 // check all the neighboring cells to see if the word can be formed by extending the path from the current position_45 // go left i-1_45 if i > 0 && dfs(board, word[1:], i-1, j) {_45 return true_45 }_45 // go right i+1_45 if i < len(board)-1 && dfs(board, word[1:], i+1, j) {_45 return true_45 }_45 // go up j-1_45 if j > 0 && dfs(board, word[1:], i, j-1) {_45 return true_45 }_45 // go down j+1_45 if j < len(board)-1 && dfs(board, word[1:], i, j+1) {_45 return true_45 }_45 // reset the current position back to its original value_45 board[i][j] = word_45 return false_45 }_45_45 // 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_45 for i := 0; i < len(board); i++ {_45 for j := 0; j < len(board); j++ {_45 if dfs(board, word, i, j) {_45 return true_45 }_45 }_45 }_45 return false_45}`

## 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
`_45func exist(board [][]byte, word string) bool {_45 // define the dfs function_45 var dfs func(board [][]byte, word string, i, j int) bool_45 dfs = func(board [][]byte, word string, i, j int) bool {_45 // check if the current character in the board matches the first character in the word_45 if board[i][j] != word {_45 return false_45 }_45 // check if the word has only one character_45 if len(word) == 1 {_45 return true_45 }_45 board[i][j] = '#'_45 // check all the neighboring cells to see if the word can be formed by extending the path from the current position_45 // go left i-1_45 if i > 0 && dfs(board, word[1:], i-1, j) {_45 return true_45 }_45 // go right i+1_45 if i < len(board)-1 && dfs(board, word[1:], i+1, j) {_45 return true_45 }_45 // go up j-1_45 if j > 0 && dfs(board, word[1:], i, j-1) {_45 return true_45 }_45 // go down j+1_45 if j < len(board)-1 && dfs(board, word[1:], i, j+1) {_45 return true_45 }_45 // reset the current position back to its original value_45 board[i][j] = word_45 return false_45 }_45_45 // 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_45 for i := 0; i < len(board); i++ {_45 for j := 0; j < len(board); j++ {_45 if dfs(board, word, i, j) {_45 return true_45 }_45 }_45 }_45 return false_45}`

## 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
`_45func exist(board [][]byte, word string) bool {_45 // define the dfs function_45 var dfs func(board [][]byte, word string, i, j int) bool_45 dfs = func(board [][]byte, word string, i, j int) bool {_45 // check if the current character in the board matches the first character in the word_45 if board[i][j] != word {_45 return false_45 }_45 // check if the word has only one character_45 if len(word) == 1 {_45 return true_45 }_45 board[i][j] = '#'_45 // check all the neighboring cells to see if the word can be formed by extending the path from the current position_45 // go left i-1_45 if i > 0 && dfs(board, word[1:], i-1, j) {_45 return true_45 }_45 // go right i+1_45 if i < len(board)-1 && dfs(board, word[1:], i+1, j) {_45 return true_45 }_45 // go up j-1_45 if j > 0 && dfs(board, word[1:], i, j-1) {_45 return true_45 }_45 // go down j+1_45 if j < len(board)-1 && dfs(board, word[1:], i, j+1) {_45 return true_45 }_45 // reset the current position back to its original value_45 board[i][j] = word_45 return false_45 }_45_45 // 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_45 for i := 0; i < len(board); i++ {_45 for j := 0; j < len(board); j++ {_45 if dfs(board, word, i, j) {_45 return true_45 }_45 }_45 }_45 return false_45}`

## 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
`_45func exist(board [][]byte, word string) bool {_45 // define the dfs function_45 var dfs func(board [][]byte, word string, i, j int) bool_45 dfs = func(board [][]byte, word string, i, j int) bool {_45 // check if the current character in the board matches the first character in the word_45 if board[i][j] != word {_45 return false_45 }_45 // check if the word has only one character_45 if len(word) == 1 {_45 return true_45 }_45 board[i][j] = '#'_45 // check all the neighboring cells to see if the word can be formed by extending the path from the current position_45 // go left i-1_45 if i > 0 && dfs(board, word[1:], i-1, j) {_45 return true_45 }_45 // go right i+1_45 if i < len(board)-1 && dfs(board, word[1:], i+1, j) {_45 return true_45 }_45 // go up j-1_45 if j > 0 && dfs(board, word[1:], i, j-1) {_45 return true_45 }_45 // go down j+1_45 if j < len(board)-1 && dfs(board, word[1:], i, j+1) {_45 return true_45 }_45 // reset the current position back to its original value_45 board[i][j] = word_45 return false_45 }_45_45 // 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_45 for i := 0; i < len(board); i++ {_45 for j := 0; j < len(board); j++ {_45 if dfs(board, word, i, j) {_45 return true_45 }_45 }_45 }_45 return false_45}`

## 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
`_45func exist(board [][]byte, word string) bool {_45 // define the dfs function_45 var dfs func(board [][]byte, word string, i, j int) bool_45 dfs = func(board [][]byte, word string, i, j int) bool {_45 // check if the current character in the board matches the first character in the word_45 if board[i][j] != word {_45 return false_45 }_45 // check if the word has only one character_45 if len(word) == 1 {_45 return true_45 }_45 board[i][j] = '#'_45 // check all the neighboring cells to see if the word can be formed by extending the path from the current position_45 // go left i-1_45 if i > 0 && dfs(board, word[1:], i-1, j) {_45 return true_45 }_45 // go right i+1_45 if i < len(board)-1 && dfs(board, word[1:], i+1, j) {_45 return true_45 }_45 // go up j-1_45 if j > 0 && dfs(board, word[1:], i, j-1) {_45 return true_45 }_45 // go down j+1_45 if j < len(board)-1 && dfs(board, word[1:], i, j+1) {_45 return true_45 }_45 // reset the current position back to its original value_45 board[i][j] = word_45 return false_45 }_45_45 // 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_45 for i := 0; i < len(board); i++ {_45 for j := 0; j < len(board); j++ {_45 if dfs(board, word, i, j) {_45 return true_45 }_45 }_45 }_45 return false_45}`

## 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
`_45func exist(board [][]byte, word string) bool {_45 // define the dfs function_45 var dfs func(board [][]byte, word string, i, j int) bool_45 dfs = func(board [][]byte, word string, i, j int) bool {_45 // check if the current character in the board matches the first character in the word_45 if board[i][j] != word {_45 return false_45 }_45 // check if the word has only one character_45 if len(word) == 1 {_45 return true_45 }_45 board[i][j] = '#'_45 // check all the neighboring cells to see if the word can be formed by extending the path from the current position_45 // go left i-1_45 if i > 0 && dfs(board, word[1:], i-1, j) {_45 return true_45 }_45 // go right i+1_45 if i < len(board)-1 && dfs(board, word[1:], i+1, j) {_45 return true_45 }_45 // go up j-1_45 if j > 0 && dfs(board, word[1:], i, j-1) {_45 return true_45 }_45 // go down j+1_45 if j < len(board)-1 && dfs(board, word[1:], i, j+1) {_45 return true_45 }_45 // reset the current position back to its original value_45 board[i][j] = word_45 return false_45 }_45_45 // 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_45 for i := 0; i < len(board); i++ {_45 for j := 0; j < len(board); j++ {_45 if dfs(board, word, i, j) {_45 return true_45 }_45 }_45 }_45 return false_45}`

## 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
`_4_4func exist(board [][]byte, word string) bool {_4 return false_4}`

## Dry Run

Let's try dry run using example below:

`_8board =_8[_8 ['A','B','C','E'],_8 ['S','F','C','S'],_8 ['A','D','E','E']_8]_8_8Given word = "ABCCED", return true.`
ijwordboard[i][j]wordreturn
00ABCCEDAA
10BCCEDSBfalse
01BCCEDBB
11CCEDFCfalse
00CCED#Cfalse
02CCEDCC
12CEDCC
02ED#Efalse
22EDEE
12D#Dfalse
21DDDtrue