Practice/Amazon/Leetcode 212. Word Search II

Leetcode 212. Word Search II

CodingMust

Problem

You are given a 2D character grid (board) and a list of target words. Your task is to find all words from the list that can be constructed by tracing a path through adjacent cells in the grid.

A valid path must follow these rules:

Start at any cell in the grid
Move only to horizontally or vertically adjacent cells (no diagonal moves)
Each cell can be used at most once per word
The sequence of letters along the path must exactly match the target word

Return all words from the input list that can be found in the grid. The order of the returned words does not matter.

Requirements

Implement a function that searches for multiple words simultaneously in a 2D character grid
Use depth-first search or backtracking to explore possible paths
Ensure each cell is visited at most once per word search path
Return all matching words found in the grid (duplicates in output should match duplicates in input)
Handle grids with repeated letters efficiently

Constraints

m == board.length (number of rows)
n == board[i].length (number of columns)
1 <= m, n <= 12
board[i][j] is a lowercase English letter
1 <= words.length <= 30,000
1 <= words[i].length <= 10
words[i] consists of lowercase English letters
All words in the words array are unique

Examples

Example 1:

` 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"]

Explanation:

"oath" can be traced: o(0,0) → a(0,1) → t(1,1) → h(2,1)
"eat" can be traced: e(1,0) → a(1,1) → t(1,2)
"pea" and "rain" cannot be formed by following adjacent cells `

Example 2:

` Input: board = [["a","b"], ["c","d"]] words = ["ab","ba","cd"]

Output: ["ab","ba","cd"]

Explanation: All three words can be found by connecting adjacent cells. `

Example 3:

` Input: board = [["a"]] words = ["a","aa"]

Output: ["a"]

Explanation: Only the single-letter word "a" can be found. `