DSA · Trie / Backtracking · #188
Word Search II
Module 84 · difficulty 4/5·⏱ 30:00starts on first keystroke
Given an `m x n` grid of characters `board` and a list of strings `words`, implement `findWords(board, words)` returning **all** words from `words` that can be constructed on the board. A word is built from letters of sequentially **adjacent** cells, where adjacent cells are horizontally or vertically neighboring. The **same cell may not be used more than once** in a single word. Return the matched words in any order (the harness normalises ordering).
Examples
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]→["eat","oath"]— "oath" snakes o(0,0)->a(0,1)->t(1,1)->h(2,1); "eat" uses e(1,0)->a(0,1)? no — e(1,3)->a(1,2)->t(1,1). "pea" and "rain" cannot be formed.board = [["a","b"],["c","d"]], words = ["abcb"]→[]— "abcb" would reuse the cell 'b', which is not allowed.board = [["a"]], words = ["a"]→["a"]— Single cell single-letter word.
Constraints
- · m == board.length
- · n == board[i].length
- · 1 <= m, n <= 12
- · board[i][j] is a lowercase English letter.
- · 1 <= words.length <= 3 * 10^4
- · 1 <= words[i].length <= 10
- · words[i] consists of lowercase English letters.
- · All strings of words are unique.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.