2D Array Word Search: Complexity and Optimization

Question

🧩 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)
}