# 🧩 Objective

Determine whether a given word is contained in a 2D Array word search.

# 🔎 Question

## 1. What are the time and space complexities of the current algorithm?

### Time complexity

Linear: $$\O(2(r * n))\$$

There are iterations through the outer and inner loops for the rows and columns occurring twice, once for the horizontal search, and once for the vertical search.

### Space complexity

Constant: $$\O(1)\$$

The only data stored is the currentSearch string that will not grow based on the size of the word search.

## 2. How can the time complexity be optimized?

• If the currentSearchIndex == 0, skip rows/columns that do not contain the first character of the word that is being searched for.

# 🚀 Implement

1. Iterate through the 2D Array for the word to find both horizontally and vertically.
2. Horizontally: Outer loop iteration is rows, inner loop iteration is columns
3. Vertically: Outer loop iteration is columns, inner loop iteration is rows

## Sample

Input

findWord(
arrayOf(
arrayOf("b", "r", "n"),
arrayOf("a", "s", "h"),
arrayOf("z", "x", "y")
),
"ash"
)


Output

true

## Code

fun findWord(wordSearch: Array<Array<String>>, word: String): Boolean {
checkArgErrors(wordSearch, word)
return horizSearch(wordSearch, word) || vertSearch(wordSearch, word)
}

fun horizSearch(wordSearch: Array<Array<String>>, word: String): Boolean {
for (r in wordSearch) {
var currentSearch = ""
var currentSearchIndex = 0
for (c in r) {
if (word.substring(currentSearchIndex, currentSearchIndex + 1).equals(c.toString())) {
currentSearch += c
currentSearchIndex++
if (currentSearch.equals(word))
return true
} else {
currentSearch = ""
currentSearchIndex == 0
}
}
}
return false
}
fun vertSearch(wordSearch: Array<Array<String>>, word: String): Boolean {
for (cIndex in 0 .. wordSearch[0].size - 1) {
var currentSearch = ""
var currentSearchIndex = 0
for (rIndex in 0 .. wordSearch.size - 1) {
println("c:\${wordSearch[rIndex][cIndex]}")
val currentChar = word.substring(currentSearchIndex, currentSearchIndex + 1)
if (currentChar.equals(wordSearch[rIndex][cIndex].toString())) {
currentSearch += currentChar
currentSearchIndex++
if (currentSearch.equals(word)) return true
} else {
currentSearch = ""
currentSearchIndex == 0
}
}
}
return false
}

fun checkArgErrors(wordSearch: Array<Array<String>>, word: String) {
val exception =
if (wordSearch.size == 0 || wordSearch[0].size == 0) "The word search cannot be empty."
else if (word.isEmpty()) "Cannot search for an empty word."
else if (word.length > wordSearch[0].size || word.length > wordSearch.size)
"The word is too long to search for within the word search."
else null
if (exception != null)
throw IllegalArgumentException(exception)
}