Find Every Dictionary Word Traceable on a Letter Board
Solve this ProblemHard30–35 min
Topics
BacktrackingRecursionTrieMatrix
Companies
Practice:LeetCode ↗GFG ↗AmazonGoogleMicrosoft
You're given a letter board and a list of candidate words. Find every word from the list that can be traced through horizontally or vertically adjacent cells, using each cell at most once per word.
Searching the board separately and completely for each word finds every match, but words sharing a common prefix pay for that shared prefix's board steps over and over — once per word. Inserting every word into a trie first, then walking the board exactly once while moving through the trie in lockstep, means a shared prefix is only ever traversed a single time: the DFS reaching a trie node marked as a complete word records it and simply continues from that same node, since it might also be partway through a longer word.
Test Case 1:
Input:board = ["HAT","ELP","SOS"], words = ["HELP","HAT","SOS","SOLE","TAP"]
Output:["HAT", "HELP", "SOLE", "SOS"]
Explanation:4 of the 5 candidate words can actually be traced on the board; "TAP" cannot.
Test Case 2:
Input:board = ["HAT","ELP","SOS"], words = ["CAT","PEA","LEAP","HOLE"]
Output:[]
Explanation:None of these words can be traced on this board.
Test Case 3:
Input:board = ["HAT","ELP","SOS"], words = ["AT"]
Output:["AT"]
Explanation:A single short word, found via A(0,1) → T(0,2).
Constraints
- ◆
1 ≤ board.length, board[0].length ≤ 6 - ◆
0 ≤ words.length ≤ 12, each word 1–10 uppercase letters - ◆
Each cell of the board may be used at most once per attempted word, and only horizontally/vertically adjacent cells may follow each other - ◆
Results are returned sorted in ascending (lexicographic) order for a stable, checkable answer
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Search the Whole Board Independently for Each Word
BruteTake each candidate word one at a time and run a complete, independent board search for it — scanning every cell as a possible starting point and exploring outward with backtracking, exactly like solving the single-word version of this problem from scratch. This is correct, but when two words share a prefix (like "HE" and "HELP"), the search for the second one re-walks the exact same opening letters the first search already confirmed, with absolutely no memory carried over between one word's search and the next.
Time
O(words.length · rows · cols · 4^L)Space
O(L)Java
1class Solution {
2 public String[] findBoardWords(String[] board, String[] words) {
3 List<String> result = new ArrayList<>();
4 for (String word : words) {
5 if (exists(board, word)) {
6 result.add(word);
7 }
8 }
9 Collections.sort(result);
10 return result.toArray(new String[0]);
11 }
12
13 private boolean exists(String[] board, String word) {
14 int n = board.length, m = board[0].length();
15 boolean[][] visited = new boolean[n][m];
16 for (int r = 0; r < n; r++) {
17 for (int c = 0; c < m; c++) {
18 if (dfs(board, word, r, c, 0, visited)) return true;
19 }
20 }
21 return false;
22 }
23
24 private boolean dfs(String[] board, String word, int r, int c, int idx, boolean[][] visited) {
25 if (idx == word.length()) return true;
26 int n = board.length, m = board[0].length();
27 if (r < 0 || r >= n || c < 0 || c >= m || visited[r][c] || board[r].charAt(c) != word.charAt(idx)) return false;
28 visited[r][c] = true;
29 boolean found = dfs(board, word, r + 1, c, idx + 1, visited)
30 || dfs(board, word, r - 1, c, idx + 1, visited)
31 || dfs(board, word, r, c + 1, idx + 1, visited)
32 || dfs(board, word, r, c - 1, idx + 1, visited);
33 visited[r][c] = false;
34 return found;
35 }
36}Optimal — Build a Trie of All Words, Search the Board Once
OptimalInsert every word into a trie first, so words sharing a prefix share the same chain of trie nodes. Then walk the board exactly once with a single DFS pass, moving one letter at a time through both the board and the trie together, in lockstep. Whenever the trie node reached marks the end of a word, that word is found — and the search keeps going from that same node, since it may also be a prefix of a longer word still being searched for. Two words that begin the same way are confirmed using the same handful of board steps, not two separate full searches.
Time
O(rows · cols · 4^L)Space
O(total letters in words)Java
1class Solution {
2 class TrieNode {
3 TrieNode[] children = new TrieNode[26];
4 String word = null;
5 }
6
7 public String[] findBoardWords(String[] board, String[] words) {
8 TrieNode root = new TrieNode();
9 for (String word : words) {
10 TrieNode node = root;
11 for (char ch : word.toCharArray()) {
12 int idx = ch - 'A';
13 if (node.children[idx] == null) node.children[idx] = new TrieNode();
14 node = node.children[idx];
15 }
16 node.word = word;
17 }
18 int n = board.length, m = board[0].length();
19 char[][] grid = new char[n][m];
20 for (int r = 0; r < n; r++) grid[r] = board[r].toCharArray();
21 List<String> result = new ArrayList<>();
22 boolean[][] visited = new boolean[n][m];
23 for (int r = 0; r < n; r++) {
24 for (int c = 0; c < m; c++) {
25 dfs(grid, r, c, root, visited, result);
26 }
27 }
28 Collections.sort(result);
29 return result.toArray(new String[0]);
30 }
31
32 private void dfs(char[][] grid, int r, int c, TrieNode node, boolean[][] visited, List<String> result) {
33 int n = grid.length, m = grid[0].length;
34 if (r < 0 || r >= n || c < 0 || c >= m || visited[r][c]) return;
35 int idx = grid[r][c] - 'A';
36 TrieNode next = node.children[idx];
37 if (next == null) return;
38 if (next.word != null) {
39 result.add(next.word);
40 next.word = null;
41 }
42 visited[r][c] = true;
43 dfs(grid, r + 1, c, next, visited, result);
44 dfs(grid, r - 1, c, next, visited, result);
45 dfs(grid, r, c + 1, next, visited, result);
46 dfs(grid, r, c - 1, next, visited, result);
47 visited[r][c] = false;
48 }
49}