Problem overview
The function exist receives a grid of letters, board: Array<CharArray>, and a word. It returns true when the word can be traced through the grid. A trace starts at any cell, then moves one cell at a time up, down, left or right, never diagonally. The cells visited must spell the word in order, a cell can be used at most once, and letters are case-sensitive.
Take the board with rows ABCE, SFCS and ADEE. The word ABCCED is on it: A at (0,0), B at (0,1), C at (0,2), the C below it at (1,2), E at (2,2) and D at (2,1). The word SEE works too, from the S at (1,3) down to the E at (2,3) and left to the E at (2,2). The word ABCB does not: the path A, B, C is fine, but the only B next to that C is the one already used.
Approach: backtracking
The word can begin anywhere, so the search tries every cell as a starting point. From a starting cell it is a depth-first search: match one letter, then ask each of the four neighbours to match the next letter. A path is abandoned at its first wrong letter, which keeps the search small in practice.
The rule that a cell can't be reused needs a record of the current path. Instead of a separate visited table, the solution overwrites the cell with '#', which is never a letter, so any later attempt to step on it fails the letter test. This is the "do" half of backtracking. The "undo" half comes after the neighbours have been tried: the cell gets its letter back, so other paths, starting elsewhere or arriving by another route, can use it.
In the worst case every cell starts a search that branches up to three ways at each of the L letters (four for the first, three after, since the cell it came from is marked), so the time is O(R * C * 4^L). In practice most branches die at the first mismatch.
Step by step
The outer function, exist:
- Loop over every row with
for (row in board.indices).indicesis the range of valid positions,0to the last one. - Loop over every column with
board[0].indices. The rows all have the same length, so the first row tells how many columns there are. - Try to start there. Call
dfs(board, word, row, col, 0), where the last argument is the index of the first letter. One success is enough, soreturn trueat once. - Return
falseafter both loops. If no start worked, the word isn't on the board.
The helper, dfs, answers whether the letters of word from index on can be traced starting at one cell:
- Succeed when every letter is matched. If
index == word.length, returntrue. This test comes first on purpose: the cell that triggered the call may lie outside the board, since the previous cell already matched the last letter. - Reject cells outside the board. A negative row or column, or one at least as large as the size, returns
false. - Reject a wrong letter. If
board[row][col]is notword[index], returnfalse. A cell on the current path holds'#', so it fails this test too. - Mark the cell as used by storing
'#'in it. - Try the four neighbours. Describe the moves as data, an array of
intArrayOf(row change, column change), and loop over it. Each neighbour is asked for the next letter,index + 1, and the answers are combined intofoundwith||. - Unmark the cell by putting
word[index]back. This must happen before returning, whether the neighbours succeeded or not, which is why the code storesfoundinstead of returning early. - Return
found.
The solution in Kotlin
class Solution {
fun exist(board: Array<CharArray>, word: String): Boolean {
for (row in board.indices) {
for (col in board[0].indices) {
if (dfs(board, word, row, col, 0)) {
return true
}
}
}
return false
}
fun dfs(board: Array<CharArray>, word: String, row: Int, col: Int, index: Int): Boolean {
if (index == word.length) {
return true
}
if (row < 0 || row >= board.size || col < 0 || col >= board[0].size) {
return false
}
if (board[row][col] != word[index]) {
return false
}
board[row][col] = '#'
var found = false
val directions = arrayOf(intArrayOf(-1, 0), intArrayOf(1, 0), intArrayOf(0, -1), intArrayOf(0, 1))
for (d in directions) {
found = found || dfs(board, word, row + d[0], col + d[1], index + 1)
}
board[row][col] = word[index]
return found
}
}
The Kotlin details worth a closer look:
Array<CharArray>is an array of rows, and each row is a primitiveCharArray. Both are mutable, soboard[row][col] = '#'changes the caller's board in place. Because every mark is undone, the board holds its original letters again whenexistreturns, whatever the answer.Charcomparisons.board[row][col]andword[index]are bothChar, so!=compares letters, and uppercase and lowercase differ.'#'is aCharliteral in single quotes.- Short-circuit
||. Infound || dfs(...)the call on the right only runs whilefoundis stillfalse. Once one neighbour completes the word, the remaining neighbours are skipped. They are still looped over, but cost nothing. - Order of the tests.
board[row][col]is read only after the bounds test, because an index outside the array throws anIndexOutOfBoundsException. The||chain in the bounds test also stops at the first true part. - Data instead of four calls.
directionsholds the four moves, so one loop replaces four near-identical calls.
Complexity
Let the board have R rows and C columns, and let L be the length of the word.
Time: O(R * C * 4^L) in the worst case. There are R * C starting cells, and a search can branch into several neighbours for each of the L letters. Mismatches cut most branches early, so typical inputs run much faster. A board full of the same letter with a word that almost matches is the kind of input that approaches the bound.
Space: O(L). The only extra memory is the call stack, with one call per letter matched so far. The board itself is reused as the visited record.
Edge cases and common mistakes
- Reusing a cell. On a board with the single row
ab, the wordabais false: after a and b, the only neighbour of b is the marked a. Without the marking, it would wrongly succeed. - Forgetting to unmark. Leaving
'#'in the cells after a failed path blocks later paths that need them, and some words that are on the board are reported as missing. It also leaves the caller's board damaged. - Case. A board with the row
AacontainsaA: the lowercase letter first, then the uppercase one next to it. TreatingaandAas the same would change other answers. - Word longer than the board. A single cell
acontainsa, but notaa, since the second letter has nowhere to go. - Diagonal moves. On the board
abovercd, the wordadis false, because a and d touch only at a corner. The wordacdbis true. - Testing the bounds too late. Reading
board[row][col]before the bounds test crashes for neighbours of edge cells.
Testing
On the board with rows ABCE, SFCS and ADEE:
ABCCEDgivestrue.SEEgivestrue.ABCBgivesfalse.Zgivesfalse.agivesfalse, since the board holds only uppercase letters.
On a board with the single row ab, ba gives true. On a board with the row Aa, aA gives true. On a 2x2 board of a, the word aaaaa gives false, because only four cells exist.
