LESSON 353 OF 541 · BACKTRACKING

Word Search in Swift: Backtracking with inout Boards

Practice O(R · C · 4^L) Read the full explanation

Given a grid of letters board and a string word, return true if word can be traced in the grid, and false otherwise.

The grid is an array of rows, and each row is an array of letters, one letter per cell. Rows are numbered from 0, top to bottom, and columns from 0, left to right.

To trace a word, start at any cell and move, one letter at a time, to a cell side by side with the current one: up, down, left or right, never diagonally. The cells must spell word in order, and each cell can be used at most once. Letters are case-sensitive: a and A are different letters.

Example 1:

Input: board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
], word = "ABCCED"
Output: true
Explanation: Start at the A in row 0, column 0, and go right to B and C,
down to the C in row 1, down to the E in row 2, and left to D:
A (0,0) -> B (0,1) -> C (0,2) -> C (1,2) -> E (2,2) -> D (2,1)

Example 2:

Input: board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
], word = "SEE"
Output: true
Explanation: S (1,3) -> E (2,3) -> E (2,2)

Example 3:

Input: board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
], word = "ABCB"
Output: false
Explanation: A -> B -> C works along the top row, but the only B next to that C
is the one the path already used, and a cell can't be used twice.

Constraints:

board has 1 to 6 rows and 1 to 6 columns, and every row has the same number of cells.
1 <= word.length <= 15
board and word contain only lowercase and uppercase English letters.

Note:

The tutorial uses backtracking: a depth-first search from every cell. One call checks one cell against one letter of word. If they match, it marks the cell as used, asks its four neighbours for the next letter, and then unmarks the cell, so that paths tried later can use it again. A path stops at its first wrong letter, which keeps the search small in practice.

In the worst case, the search from each of the R·C cells branches into 4 directions for each of the L letters of word (3 after the first, since the cell it came from is used): O(R·C·4^L) time, where R and C are the numbers of rows and columns and L is the length of word. The extra space is O(L), one call per letter matched so far.

STEP 1 OF 17

Guided

Ctrl + Enter to check

Word Search in Swift, explained

Problem overview

The method exist(_ board: [[Character]], _ word: String) -> Bool receives a grid of letters, an array of rows, and a word. It returns true if the word can be traced through the grid. A trace starts at any cell and moves to a neighbour above, below, left or right, never diagonally. The cells must spell the word in order, a cell can be used at most once, and letters are case-sensitive.

Take the grid ABCE / SFCS / ADEE (three rows of four letters). "ABCCED" is found: A at row 0, column 0, then B, then C in row 0, down to the C in row 1, down to the E in row 2, and left to D. "SEE" is also found, from the S at row 1, column 3 down through two Es. "ABCB" is not: the only B next to the second C is the B the path already used.

Approach: depth-first search with backtracking

The word can start anywhere, so try every cell as the first letter. From a start, follow the word one letter at a time. A call looks at one cell and one position in the word. If the cell holds the wrong letter, that path is dead. If it holds the right letter, the call asks its four neighbours to match the next letter.

Two details make this correct. First, a cell can't be reused on the same path, so a cell on the path is marked while the search goes deeper. Second, the mark must be removed on the way back. That is the backtracking step: after a path fails, the same cell may belong to a different path tried later, so the board has to look exactly as it did before the visit.

The search stops at the first wrong letter, which keeps it small in practice. In the worst case, with R rows, C columns and a word of length L, each of the R * C starts branches into up to 3 new directions per letter after the first, so the bound is O(R * C * 4^L), and the grid is at most 6 by 6 with a word of at most 15 letters.

Step by step

Make a board you can change. Swift parameters are constants, and the search writes marks into the board. var board = board declares a variable with the same name that starts as a copy of the parameter and hides it for the rest of the function.
Turn the word into an array of characters. A String can't be indexed with an integer, but Array(word) can. Again the new word hides the parameter.
Loop over every row and column with 0..<board.count and 0..<board[0].count, so each cell gets a turn as the first letter.
Call dfs for each start with &board, word, the cell and index 0. If it returns true, return true at once: one successful start is enough.
Return false after the loops. No cell could start the word.
Declare dfs with the board as an inout [[Character]], the word, a row, a column and an index: the position in the word of the letter this cell must hold.
Succeed when every letter is matched. If index == word.count, return true. This test comes first because the cell that triggered it may lie outside the board: the previous cell matched the last letter, so this one doesn't matter.
Reject cells outside the board. Four comparisons joined with || cover row and column below zero or past the end.
Reject a wrong letter. If board[row][col] != word[index], return false. A cell already on the path holds "#", which is not a letter, so this test also keeps a path from stepping on itself.
Mark the cell by writing "#" into it.
Prepare found and the four moves. found starts as false. directions lists up, down, left and right as (row change, column change) pairs, so one loop replaces four copies of the same call.
Ask each neighbour for the next letter. found = found || dfs(...) uses index + 1 and the shifted row and column.
Unmark the cell by writing word[index] back, the letter it held when it matched.
Return found. The result is held in a variable, instead of returned the moment a neighbour succeeds, because the cell has to be unmarked first.

The solution in Swift

class Solution {
    func exist(_ board: [[Character]], _ word: String) -> Bool {
        var board = board
        let word = Array(word)
        for row in 0..<board.count {
            for col in 0..<board[0].count {
                if dfs(&board, word, row, col, 0) {
                    return true
                }
            }
        }
        return false
    }

    func dfs(_ board: inout [[Character]], _ word: [Character], _ row: Int, _ col: Int, _ index: Int) -> Bool {
        if index == word.count {
            return true
        }
        if row < 0 || row >= board.count || col < 0 || col >= board[0].count {
            return false
        }
        if board[row][col] != word[index] {
            return false
        }
        board[row][col] = "#"
        var found = false
        let directions = [[-1, 0], [1, 0], [0, -1], [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 Swift details worth a closer look:

inout and &. A parameter marked inout lets the function change the caller's variable, and the caller writes & before the argument. Every dfs call then shares one board. Without inout, the parameter would be a constant, and assigning to board[row][col] would be a compile error.
Arrays are values. var board = board copies, so the caller's grid is never touched. The marks live in the local copy, and after exist returns, the caller's board still holds its letters.
Short-circuit ||. The right side of found || dfs(...) runs only while found is still false. Once one direction finishes the word, the remaining directions are skipped. The loop still goes through all four moves, but the later calls do no work.
Character literals. "#" is read as a Character here because the board holds characters. The same double-quoted literal is a string elsewhere.
Nested array indexing. board[row][col] reads the row, then the cell. board[0].count is the column count, which the constraints guarantee is the same for every row.

Complexity

Time: O(R * C * 4^L) in the worst case, as described above, and much faster when most paths fail on the first letters.

Space: O(L) beyond the board copy. Each active call matches one letter, so the recursion is at most L calls deep.

Edge cases and common mistakes

Forgetting to unmark. Leave out the line that restores word[index] and a failed path leaves its cells marked for every later path. On the grid AA / AB (rows ["A", "A"] and ["A", "B"]), the word "AAA" should be found by going from the top right A to the top left A to the bottom left A. If the search starts at the top left A and fails first, it leaves that cell and its neighbour marked, and the version without the restore returns false. The lesson's solution returns true.
Reusing a cell. The marker is what stops "ABCB" from reusing a B. Skip the marking and that word would be accepted.
Checking the word's end after the bounds. A path that matches the last letter makes its last call at a neighbour, possibly outside the board. Testing index == word.count first avoids rejecting a finished path.
Case. a and A are different letters, so a one-cell board [["A"]] doesn't contain "a".
Words longer than the board. "aa" on a single cell a returns false: the cell can't be used twice.
Diagonals. Only four moves exist, so letters that touch at a corner are not neighbours.

Testing

With the grid ABCE / SFCS / ADEE:

"ABCCED" gives true.
"SEE" gives true.
"ABCB" gives false.
"SFB" gives true.
"ABCESEEEFS" gives false.

With one-cell and tiny grids:

[["a"]] with "a" gives true, and with "aa" gives false.
[["a", "a"]] with "aaa" gives false.
[["A", "B"]] with "BA" gives true.

Keep going with Swift500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free