Word Search II
The briefingthe full drill, in my own words
The drill: A letter grid and a list of candidate words — report every candidate that can actually be traced out by stepping to horizontally or vertically adjacent cells, never reusing a cell inside the same word.
A letter grid and a list of candidate words arrive together. For each candidate, the question is whether it can be traced by stepping to horizontally or vertically adjacent cells, one letter per step, never reusing a cell within that word's own path.
The output is the list of candidates that actually succeed — every word that can't be traced on the board is simply left out, and a word that appears twice in the candidate list should still only be reported once.
Different candidate words may reuse the very same cells on the board; the no-reuse rule only applies within a single word's own path, not across separate words.
- grids stay modest, typically a few hundred cells
- candidate words are generally short, well under twenty letters each
- a single word's path never reuses the same cell twice
- each qualifying candidate is reported once, even if listed multiple times
The hintstake only what you need
HINT 1 THE NUDGE
Running the single-word board search once per candidate re-walks the same grid from scratch every time — most of that work retraces paths that no candidate even starts with. What if every candidate's search could share its early steps?
HINT 2 THE STRUCTURE
Words with the same prefix should share the same walk down the board until they actually diverge — that's exactly the shape a trie stores, letter by letter.
HINT 3 ONE STEP FROM THE ANSWER
Merge all the candidate words into one trie first, then do a single backtracking scan of the board following trie edges instead of blind neighbors. Whenever the node you land on is marked as a complete word, record it and clear that mark so it's never recorded twice.
Coach's boardthe pattern, step by step
Words an, ant, at merge into one trie: a branches to n (word 'an', continuing to t for 'ant') and to t (word 'at').
The splitstwo paces, two languages
class TrieNode:
def __init__(self):
self.children = {}
self.word = None # the full word, set only at a terminal node
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
root = TrieNode()
for w in words:
node = root
for ch in w:
node = node.children.setdefault(ch, TrieNode())
node.word = w
rows, cols = len(board), len(board[0])
result = []
def dfs(r: int, c: int, node: TrieNode) -> None:
ch = board[r][c]
child = node.children.get(ch)
if child is None:
return
if child.word is not None:
result.append(child.word)
child.word = None # never report the same word twice
board[r][c] = "#"
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":
dfs(nr, nc, child)
board[r][c] = ch
if not child.children:
del node.children[ch] # dead branch, prune it for later scans
for r in range(rows):
for c in range(cols):
dfs(r, c, root)
return resultclass Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
rows, cols = len(board), len(board[0])
def exists(word: str) -> bool:
def dfs(r: int, c: int, i: int) -> bool:
if i == len(word):
return True
if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[i]:
return False
tmp = board[r][c]
board[r][c] = "#"
found = (
dfs(r + 1, c, i + 1)
or dfs(r - 1, c, i + 1)
or dfs(r, c + 1, i + 1)
or dfs(r, c - 1, i + 1)
)
board[r][c] = tmp
return found
for r in range(rows):
for c in range(cols):
if dfs(r, c, 0):
return True
return False
return [w for w in words if exists(w)]class WsTrieNode {
Map<Character, WsTrieNode> children = new HashMap<>();
String word = null; // the full word, set only at a terminal node
}
class Solution {
private char[][] board;
private int rows, cols;
private List<String> result;
public List<String> findWords(char[][] board, String[] words) {
WsTrieNode root = new WsTrieNode();
for (String w : words) {
WsTrieNode node = root;
for (char c : w.toCharArray()) {
node = node.children.computeIfAbsent(c, k -> new WsTrieNode());
}
node.word = w;
}
this.board = board;
this.rows = board.length;
this.cols = board[0].length;
this.result = new ArrayList<>();
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
dfs(r, c, root);
}
}
return result;
}
private void dfs(int r, int c, WsTrieNode node) {
char ch = board[r][c];
WsTrieNode child = node.children.get(ch);
if (child == null) {
return;
}
if (child.word != null) {
result.add(child.word);
child.word = null; // never report the same word twice
}
board[r][c] = '#';
int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] != '#') {
dfs(nr, nc, child);
}
}
board[r][c] = ch;
if (child.children.isEmpty()) {
node.children.remove(ch); // dead branch, prune it for later scans
}
}
}class Solution {
private char[][] board;
private int rows, cols;
public List<String> findWords(char[][] board, String[] words) {
this.board = board;
this.rows = board.length;
this.cols = board[0].length;
List<String> result = new ArrayList<>();
for (String w : words) {
if (exists(w)) {
result.add(w);
}
}
return result;
}
private boolean exists(String word) {
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (dfs(r, c, word, 0)) {
return true;
}
}
}
return false;
}
private boolean dfs(int r, int c, String word, int i) {
if (i == word.length()) {
return true;
}
if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != word.charAt(i)) {
return false;
}
char tmp = board[r][c];
board[r][c] = '#';
boolean found = dfs(r + 1, c, word, i + 1)
|| dfs(r - 1, c, word, i + 1)
|| dfs(r, c + 1, word, i + 1)
|| dfs(r, c - 1, word, i + 1);
board[r][c] = tmp;
return found;
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED