Find All Dictionary Words in a Letter Grid
Problem
Given a 2D grid of letters and a list of dictionary words, return every word that can be formed by following adjacent (4-directional) cells without reusing a cell.
Insert all words into a trie, with the word stored at its terminal node. DFS from each cell carrying a trie pointer; before exploring a neighbour, advance the trie pointer by that letter. As soon as the trie has no such child, prune. Whenever the current node holds a stored word, record it and clear the slot to avoid duplicates.
Input
grid = [[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" follows (0,0)→(1,1)→(2,1)→(3,1); "eat" follows (1,3)→(1,2)→(0,2). "pea" and "rain" don't trace.
def find_words(grid, words):
root = {}
for w in words:
n = root
for c in w: n = n.setdefault(c, {})
n["$"] = w
out = []
R, C = len(grid), len(grid[0])
def dfs(r, c, n):
ch = grid[r][c]
if ch not in n: return
nxt = n[ch]
if "$" in nxt:
out.append(nxt["$"]); del nxt["$"]
grid[r][c] = "#"
for dr, dc in ((-1,0),(1,0),(0,-1),(0,1)):
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != "#":
dfs(nr, nc, nxt)
grid[r][c] = ch
for r in range(R):
for c in range(C): dfs(r, c, root)
return outfunction findWords(grid, words) {
const root = {};
for (const w of words) {
let n = root;
for (const c of w) n = n[c] || (n[c] = {});
n.$ = w;
}
const out = [], R = grid.length, C = grid[0].length;
function dfs(r, c, n) {
const ch = grid[r][c];
if (!n[ch]) return;
const nx = n[ch];
if (nx.$) { out.push(nx.$); delete nx.$; }
grid[r][c] = "#";
for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]]) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] !== "#") dfs(nr, nc, nx);
}
grid[r][c] = ch;
}
for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) dfs(r, c, root);
return out;
}static class Node { Map<Character, Node> ch = new HashMap<>(); String word; }
List<String> out = new ArrayList<>();
char[][] g; int R, C;
public List<String> findWords(char[][] grid, String[] words) {
g = grid; R = grid.length; C = grid[0].length;
Node root = new Node();
for (String w : words) {
Node n = root;
for (char c : w.toCharArray()) n = n.ch.computeIfAbsent(c, k -> new Node());
n.word = w;
}
for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) dfs(r, c, root);
return out;
}
void dfs(int r, int c, Node n) {
char ch = g[r][c];
Node nx = n.ch.get(ch);
if (nx == null) return;
if (nx.word != null) { out.add(nx.word); nx.word = null; }
g[r][c] = '#';
int[][] D = {{-1,0},{1,0},{0,-1},{0,1}};
for (int[] d : D) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr][nc] != '#') dfs(nr, nc, nx);
}
g[r][c] = ch;
}struct Node { unordered_map<char, Node*> ch; string word; };
vector<string> out;
int R, C;
vector<vector<char>>* gp;
void dfs(int r, int c, Node* n) {
char ch = (*gp)[r][c];
if (!n->ch.count(ch)) return;
Node* nx = n->ch[ch];
if (!nx->word.empty()) { out.push_back(nx->word); nx->word.clear(); }
(*gp)[r][c] = '#';
int D[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
for (auto& d : D) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && (*gp)[nr][nc] != '#') dfs(nr, nc, nx);
}
(*gp)[r][c] = ch;
}