79.word-search.md

79. Word Search

Key Insights

• Search starts from every cell, because we don't know where the word begins.
• Must avoid revisiting the same cell in the same path, but we can revisit the same cell in different paths.
• Stop early once the full word is matched.

DFS (Path Finding)

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 {
    val m = board.size
    val n = board[0].size
    if (x !in 0 until m || y !in 0 until n) return false
    if (x to y in visited) return false
    if (board[x][y] != word[index]) return false
    if (index == word.length - 1) return true

    visited.add(x to y)
    for (d in directions) {
        val newX = x + d[0]
        val newY = y + d[1]
        if (dfs(board, newX, newY, index + 1, word, visited)) return true
    }
    // Remember to backtrack
    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.

Why Backtracking?

One cell can be used multiple times in different paths, but only once in one path. For example, the board is:

A B
C D

(0, 0) A  (0, 1) B
(1, 0) C  (1, 1) D

The path from A to D can be:

• Path 1: A -> B -> D
• Path 2: A -> C -> D

If we visit the first path A -> B -> D, but we don't backtrack, then we won't visit D in the second path A -> C -> D because D is already visited.

Let's take a look at the following example which leads to WA if we don't backtrack:

A E
E E
E X

(0,0) A   (0,1) E1
(1,0) E2  (1,1) E3
(2,0) E4  (2,1) X

word = "A, E, E, E, E, X"

// Expected path: A -> E1 -> E3 -> E2 -> E4 -> X

// Visited set if we don't backtrack:
(0, 0) = A
(0, 1) = E1
(1, 1) = E3
(1, 0) = E2
(2, 0) = E4
-> Dead end