Find All Words on a Board

Given a grid of letters and a list of words, identify all words from the list that can be constructed by traversing adjacent cells in the grid. This problem tests your ability to combine graph traversal with efficient data structures for searching.

triedepth-first searchbacktrackinggraph traversalstring searching

Problem Statement

You are given a two-dimensional array (matrix) of characters representing a letter grid and a list of strings representing a dictionary of words. Your task is to find all the words from the dictionary that can be formed by connecting adjacent letters in the grid. 'Adjacent' means horizontally or vertically neighboring cells. Each cell can only be used once in the formation of a single word.

Example 1

Input: board = [['A', 'B', 'C', 'E'], ['S', 'F', 'C', 'S'], ['A', 'D', 'E', 'E']], words = ['ABCCED', 'SEE', 'ADEE', 'ABC']

Output: ['ABCCED', 'SEE', 'ADEE']

'ABCCED' can be found starting at (0,0), 'SEE' can be found starting at (1,0) or (2,2), and 'ADEE' can be found starting at (2,0). 'ABC' cannot be found.

Example 2

Input: board = [['o', 'a', 'a', 'n'], ['e', 't', 'a', 'e'], ['i', 'h', 'k', 'r'], ['i', 'f', 'l', 'v']], words = ['oath', 'pea', 'eat', 'rain']

Output: ['oath', 'eat']

'oath' can be found starting at (0,0), 'eat' can be found starting at (1,1). 'pea' and 'rain' cannot be found.

Constraints

-1 <= board.length <= 200
-1 <= board[i].length <= 200
-1 <= words.length <= 10^3
-1 <= words[i].length <= 10
-board[i][j] and words[i] consist of lowercase and uppercase English letters.

Brute Force Approach

The brute force approach would involve iterating through each word in the word list and, for each word, scanning the entire board to see if the first letter exists. If it does, we'd perform a depth-first search (DFS) to see if the rest of the word can be formed. Imagine you have a list of errands (words) and you walk through every possible street (board) trying to find each errand location. This is inefficient because you're repeating the search process for each errand. Time complexity is very high, and the space complexity is relatively low since we mostly use existing data structures.

TimeO(m * n * 4^k * w)

SpaceO(k)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem