79.word-search.md

79. Word Search

TODO: Notes

private val directions = arrayOf(
    intArrayOf(-1, 0),
    intArrayOf(1, 0),
    intArrayOf(0, -1),
    intArrayOf(0, 1)
)

fun exist(board: Array<CharArray>, word: String): Boolean {
    for (i in 0 until board.size) {
        for (j in 0 until board[0].size) {
            if (dfs(board, i, j, 0, word, hashSetOf<Pair<Int, Int>>())) return true
        }
    }
    return false
}

private fun dfs(board: Array<CharArray>, x: Int, y: Int, index: Int, word: String, visited: HashSet<Pair<Int, Int>>): Boolean {
    if (x < 0 || x >= board.size || y < 0 || y >= board[0].size || visited.contains(x to y) || board[x][y] != word[index]) return false
    
    if (index == word.length - 1) {
        return true
    }

    visited.add(x to y)
    directions.forEach { d -> 
        val newX = x + d[0]
        val newY = y + d[1]
        if (dfs(board, newX, newY, index + 1, word, visited)) return true
    }
    // Backtracking
    visited.remove(x to y)
    return false
}

• Time Complexity: O(m * n * 3^L), m * n is the size of board, L is the length of word, for every starting search position, there are 3 directions will search.
• Space Complexity: O(min(L, m * n)) for DFS recursive function call stack, it's either found or search all letter.