Word Search

Medium

The problem

Given a grid of letters and a word, return true if the word can be spelled by moving step by step through touching cells (up, down, left or right). The same cell cannot be used twice in one spelling.

Example 1
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Example 2
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
Example 3
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
After A → B → C, the only B nearby has already been used.

Limits

1 ≤ rows, columns ≤ 6
1 ≤ word.length ≤ 10
Letters are English letters; uppercase and lowercase are different

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

From each cell, try the four directions for the next letter — but a cell cannot be used twice in one path.

The idea

DFS from every cell matching word[0]; mark the cell visited, recurse into the 4 neighbours for the next letter, then un-mark.

Target: O(m·n·3^L) time

Go function shape

func exist(board [][]byte, word string) bool

Reference solution

Tested with go test. Try it yourself first, then compare.

// Exist: is `word` traceable through adjacent cells, using each cell once?
// Mark a cell as used while exploring it, restore it afterwards.
func Exist(board [][]byte, word string) bool {
	if len(word) == 0 {
		return true
	}
	var dfs func(r, c, k int) bool
	dfs = func(r, c, k int) bool {
		if r < 0 || c < 0 || r >= len(board) || c >= len(board[r]) || board[r][c] != word[k] {
			return false
		}
		if k == len(word)-1 {
			return true
		}
		saved := board[r][c]
		board[r][c] = '#' // choose: mark visited
		found := dfs(r+1, c, k+1) || dfs(r-1, c, k+1) || dfs(r, c+1, k+1) || dfs(r, c-1, k+1)
		board[r][c] = saved // un-choose
		return found
	}
	for r := range board {
		for c := range board[r] {
			if dfs(r, c, 0) {
				return true
			}
		}
	}
	return false
}

Read the lesson: Backtracking