Skip to content
AI360Xpert
Back to Tries
Hard

Word Search II

Given an `m x n` `board` of characters and a list of strings `words`, return all words on the board. Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Examples

Input:board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output:["eat","oath"]
Input:board = [["a","b"],["c","d"]], words = ["abcb"]
Output:[]

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 the strings of words are unique.

Trie + Backtracking (DFS)

Approach

Searching for every word individually using DFS takes O(W * m * n * 4^L) which is too slow. Instead, build a Trie containing all the `words`. Then, run a DFS starting from every cell on the board. As we traverse the board, we simultaneously traverse the Trie. If a board cell's character exists as a child in the Trie, we proceed. If we hit a Trie node that marks the end of a word, we found a match and add it to our results. We use a visited set (or mark the board cell temporarily) to avoid reusing cells in the same path. To optimize, remove words from the Trie once found to avoid duplicate work.

Complexity Analysis

Time Complexity
O(M * N * 4^L)
Space Complexity
O(W * L)

M, N are board dimensions. L is the max length of a word. W is the number of words. The Trie significantly prunes the DFS search space.

Solution.java
class TrieNode {    TrieNode[] children = new TrieNode[26];    String word = null; // Store the word at the end node}
class Solution {    List<String> res = new ArrayList<>();    char[][] board;        public List<String> findWords(char[][] board, String[] words) {        this.board = board;                // Build Trie        TrieNode root = new TrieNode();        for (String w : words) {            TrieNode curr = root;            for (char c : w.toCharArray()) {                int index = c - 'a';                if (curr.children[index] == null) {                    curr.children[index] = new TrieNode();                }                curr = curr.children[index];            }            curr.word = w; // Mark end of word        }                // DFS from each cell        for (int r = 0; r < board.length; r++) {            for (int c = 0; c < board[0].length; c++) {                dfs(r, c, root);            }        }                return res;    }        private void dfs(int r, int c, TrieNode node) {        if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] == '#') {            return;        }                char letter = board[r][c];        TrieNode currNode = node.children[letter - 'a'];        if (currNode == null) return;                // Check if we found a word        if (currNode.word != null) {            res.add(currNode.word);            currNode.word = null; // Prevent duplicate additions        }                // Mark cell as visited        board[r][c] = '#';                // Explore neighbors        dfs(r - 1, c, currNode); // Up        dfs(r + 1, c, currNode); // Down        dfs(r, c - 1, currNode); // Left        dfs(r, c + 1, currNode); // Right                // Restore cell (backtracking)        board[r][c] = letter;    }}