Start learning free

LESSON 352 OF 540 · BACKTRACKING

Word Search in Go: Backtracking, O(R·C·4^L)

Practice O(R · C · 4L) 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·4L) 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 15
    Ctrl + Enter to check

    GO · BACKTRACKING

    Word Search in Go, explained

    Problem overview

    The function exist receives a grid of letters, board (a [][]byte), and a string word. It returns true when the word can be traced through the grid and false otherwise. A trace starts at any cell and moves one step at a time to the cell above, below, left or right, never diagonally. The cells visited must spell word in order, no cell can be used twice in one trace, and letters are case-sensitive.

    Take this board:

    A B C E
S F C S
A D E E

    "ABCCED" can be traced: A at (0,0), B at (0,1), C at (0,2), C at (1,2), E at (2,2), D at (2,1). "SEE" works too, with S at (1,3), E at (2,3) and E at (2,2). "ABCB" fails: A, B, C is fine along the top row, but the only B next to that C is the one already used.

    Approach: depth-first search with backtracking

    The word can start in any cell, so the function tries every cell as the first letter. From a cell that matches, it asks the four neighbours to match the next letter, then theirs, and so on. A path is abandoned at its first wrong letter, which keeps the search small in practice.

    Two things make this work:

    • Marking cells as used. While a cell is on the current path, it is overwritten with '#'. The board contains only letters, so a marked cell can never match a letter of the word, and deeper calls can't step on it again.
    • Unmarking on the way back. When a call has tried all four neighbours, it puts its letter back. A different path, tried later, may need that cell. This undo is the backtracking.

    In the worst case the search starts from each of the R·C cells and branches into up to four directions for each of the L letters (three after the first, since the cell it came from is marked), so the time is O(R·C·4^L). The constraints keep the board at most 6 by 6 and the word at most 15 letters, and the early stop at wrong letters makes real inputs much cheaper than the worst case.

    Step by step

    The outer function

    1. Loop over the rows with for row := range board. With one variable, range over a slice yields the indexes.
    2. Loop over the columns of that row with for col := range board[row]. Together the two loops visit every cell as a possible start.
    3. Call dfs with the board, the word, the cell and index 0, the first letter. If it returns true, return true at once: one successful start is enough.
    4. Return false after both loops. No start worked.

    The helper dfs

    1. Write the signature. It takes the board, the word, a cell and index, the position in word of the letter this cell must hold. It reports whether the letters from index to the end can be traced starting at the cell.
    2. Everything matched. If index == len(word), return true. This test comes first, because the cell that matched the last letter has already done its job, and the next cell may even lie outside the board.
    3. Outside the board. Return false when the row or column is below 0 or past the last row or column. Testing here means no caller has to check its neighbours.
    4. Wrong letter. Return false when board[row][col] differs from word[index]. Both are bytes, so they compare directly. A cell already on the path holds '#' and fails this test too.
    5. Mark the cell by setting it to '#'.
    6. Start with found := false. The function can't return as soon as a neighbour succeeds, because the cell has to be unmarked first.
    7. Write the four moves as data: directions is a [][2]int of {row change, column change} pairs. One loop then replaces four copies of the same call.
    8. Loop over the moves. For each d, set found = found || dfs(...) on the neighbour at row+d[0], col+d[1] with index+1.
    9. Unmark the cell by writing word[index] back into it.
    10. Return found.

    The solution in Go

    func exist(board [][]byte, word string) bool {
	for row := range board {
		for col := range board[row] {
			if dfs(board, word, row, col, 0) {
				return true
			}
		}
	}
	return false
}

func dfs(board [][]byte, word string, row int, col int, index int) bool {
	if index == len(word) {
		return true
	}
	if row < 0 || row >= len(board) || col < 0 || col >= len(board[0]) {
		return false
	}
	if board[row][col] != word[index] {
		return false
	}
	board[row][col] = '#'
	found := false
	directions := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
	for _, d := range directions {
		found = found || dfs(board, word, row+d[0], col+d[1], index+1)
	}
	board[row][col] = word[index]
	return found
}

    Go details worth knowing:

    • Bytes against bytes. board is a [][]byte and word[index] is a byte, so they compare without conversion. '#' is an untyped constant that becomes a byte when assigned to a cell.
    • The board is shared, not copied. A slice of slices passed to a function still points at the same cells, so marking a cell in a deep call is visible to every call above it. That is what makes the marks work, and it is why the unmarking step is required: nothing restores the board automatically.
    • [2]int is an array of exactly two ints, a fixed-size value, which suits a pair of offsets. [][2]int is a slice of such pairs.
    • Short-circuit ||. The right side of found || dfs(...) runs only while found is still false, so once a neighbour completes the word, the others are skipped. The loop still reaches the unmarking line, which is what we want.
    • range board[row] gives the columns of that row, which also works for rows of different lengths. The bounds test uses len(board[0]), which is right here because every row has the same width.

    Complexity

    Time: O(R·C·4^L), where R and C are the board's rows and columns and L is the length of word. There are R·C starting cells, and each search goes at most L letters deep with at most four choices per level. The bound is loose, because marked cells and wrong letters cut paths early.

    Space: O(L) for the recursion: one call per letter matched so far. The marks live in the board itself, so no visited array is needed.

    Edge cases and common mistakes

    • Forgetting to unmark. The search then leaves '#' in cells that failed paths passed through, and later paths can't use them. On the board ["AAAB"] (one row) with the word "AAB", the correct function returns true, but a version without the unmarking line returns false: the first attempt, from the leftmost A, marks cells and fails, and the successful path needs one of them.
    • Reusing a cell. Without marking, the one-row board ["AB"] would trace "ABA" by stepping back onto the first A. With marking, exist returns false for it.
    • Checking the bounds after reading the cell. Reading board[row][col] before the bounds test panics with an index out of range at an edge.
    • Testing the end of the word too late. If the index == len(word) test came after the bounds test, a word ending at the edge of the board would fail, since the call after the last letter steps outside.
    • Case. a and A are different letters. On the example board, "A" is found and "a" isn't.
    • The board is modified during the search. It is restored by the time exist returns, as long as every mark is undone, so the caller sees the original board.

    Testing

    On the 3 by 4 board above (ABCE, SFCS, ADEE):

    • "ABCCED" gives true.
    • "SEE" gives true.
    • "ABCB" gives false.
    • "SFCE" gives true.
    • "ASA" gives true (down the first column).
    • "A" gives true and "a" gives false.

    On one-row boards: ["a"] with "a" gives true, ["a"] with "aa" gives false, and ["aa"] with "aaa" gives false.

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