Word Search II: the idea to remember.

The core insight

Build a trie, then backtrack through board paths and trie edges together. Stop immediately when a prefix has no matching edge.

Why it works

Every valid dictionary path is explored, while a missing trie edge proves that no dictionary word can complete that board prefix.

The mistake to avoid

Clear a found terminal word to avoid duplicate output, but continue exploring because it may be a prefix of another word. Restore each board cell.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

class TNode { TNode[] next = new TNode[26]; String word; }
List<String> findWords(char[][] board, String[] words) {
    TNode root = new TNode();
    for (String word : words) {
        TNode node = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a'; if (node.next[i] == null) node.next[i] = new TNode(); node = node.next[i];
        }
        node.word = word;
    }
    List<String> out = new ArrayList<>();
    for (int r = 0; r < board.length; r++) for (int c = 0; c < board[0].length; c++) searchWords(board, r, c, root, out);
    return out;
}
void searchWords(char[][] b, int r, int c, TNode parent, List<String> out) {
    if (r < 0 || r >= b.length || c < 0 || c >= b[0].length || b[r][c] == '#') return;
    char value = b[r][c]; TNode node = parent.next[value - 'a']; if (node == null) return;
    if (node.word != null) { out.add(node.word); node.word = null; }
    b[r][c] = '#';
    searchWords(b,r+1,c,node,out); searchWords(b,r-1,c,node,out);
    searchWords(b,r,c+1,node,out); searchWords(b,r,c-1,node,out);
    b[r][c] = value;
}

Make the next connection