Close

# Mohit Athwani

MA

In this problem, we are given a two dimensional board of characters and we have to check if the word can be found in the board by checking adjacent cells only.

A basic strategy to solve this problem would be to start walking down the board until the first character is found. Once the first character is found, look at the character one row above, below, one column to the left and only column to the right to see if the second character in the string can be matched. If the second character is found, we look around that position and we go on and on if the characters are found. Before we go on exploring surrounding cells, we need to make sure that we have not visited it before and if we have, we just skip it. We can maintain a `[[Bool]]` to help us keep track of visited and unvisited cells.

This brings us to implementing a recursive strategy and if you think about it, it is pretty similar to Depth First Search.

There are some base cases that need to be handled like if the `numRows` and `numCols` are zero and if the search term is empty. Perhaps a base case that I totally missed and helps us completely avoid going into the recursion is checking if the size of the search term is greater than the product of the `numRows` and `numCols`, because if it is then there is no sense in proceeding.

The code for this as shown:

```func dfs(i: Int, j: Int, index: Int, chars: [Character], board:[[Character]], map:inout [[Bool]]) -> Bool {

let topRow = i - 1
let bottomRow = i + 1
let leftColumn = j - 1
let rightColumn = j + 1

let numRows = board.count
let numCols = board[0].count

let isLastChar = index == chars.count - 1

if isLastChar {
return board[i][j] == chars[index]
}

if topRow >= 0 && !map[topRow][j] && !isLastChar && board[topRow][j] == chars[index + 1] {
map[topRow][j] = true
let result = dfs(i: topRow, j: j, index: index + 1, chars: chars, board: board, map: &map)
if result == true {
return true
}
map[topRow][j] = false
}

if bottomRow < numRows && !map[bottomRow][j] && !isLastChar && board[bottomRow][j] == chars[index + 1] {
map[bottomRow][j] = true
let result = dfs(i: bottomRow, j: j, index: index + 1, chars: chars, board: board, map: &map)
if result == true {
return true
}
map[bottomRow][j] = false
}

if leftColumn >= 0 && !map[i][leftColumn] && !isLastChar && board[i][leftColumn] == chars[index + 1] {
map[i][leftColumn] = true
let result = dfs(i: i, j: leftColumn, index: index + 1, chars: chars, board: board, map: &map)
if result == true {
return true
}
map[i][leftColumn] = false
}

if rightColumn < numCols && !map[i][rightColumn] && !isLastChar && board[i][rightColumn] == chars[index + 1] {
map[i][rightColumn] = true
let result = dfs(i: i, j: rightColumn, index: index + 1, chars: chars, board: board, map: &map)
if result == true {
return true
}
map[i][rightColumn] = false
}

return false
}

func exist(_ board: [[Character]], _ word: String) -> Bool {

let numRows = board.count
let numCols = numRows > 0 ? board[0].count : 0
let chars = Array(word)

if numRows == 0 || numCols == 0 || word.isEmpty{
return false
}

if word.count >  numRows * numCols {
return false
}

var map = board.map { (row) -> [Bool] in
row.map({ (c) -> Bool in
return false
})
}

for i in stride(from: 0, to: numRows, by: 1) {
for j in stride(from: 0, to: numCols, by: 1) {
if board[i][j] == chars[0] {
map[i][j] = true
let result = dfs(i: i, j: j, index: 0, chars: chars, board: board, map: &map)
if result == true {
return true
}
map[i][j] = false
}
}
}
return false
}```

The time complexity is `O(N)` where `N` is the length of the search term as we only have to enter recursion if all characters until `i-1` in the search term have been matched. There could be a situation in which the first character is never found while iterating through the board and in that case the time complexity is `O(RC)` in terms of the rows and columns.

The space complexity is `O(RC)` in terms of the rows and columns in the board as we maintain an additional two dimensional array to maintain the visited states.

The problem is taken from Leetcode.

The code is hosted on Github.

#### Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.