Start learning free

LESSON 427 OF 536 · TRIES

Word Search II in Java: Trie and Backtracking

Practice O(R · C · 4L) Read the full explanation

Given a grid of letters board with R rows and C columns, and an array of strings words, return every word of words that can be traced on the board.

A word is traced by a path of cells: its first letter is in some cell, and each next letter is in a cell next to the previous one, horizontally or vertically (not diagonally). A cell can be used only once in the same word.

Return each word found once, in any order: the output lists the words in alphabetical order. If no word can be traced, the answer is empty.

 

Example 1:

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"]
Explanation: "oath" starts at the top-left "o", goes right to "a", down to "t" and down again to "h".
"eat" starts at the "e" at the right end of the second row, then goes left to "a" and left again to "t".
The board has no "p", so "pea" can't be traced, and no "a" is next to the "r", so neither can "rain".

Example 2:

Input: board = [
  ["a", "b"],
  ["c", "d"]
], words = ["abdb", "ad"]
Output: []
Explanation: "abdb" would go a → b → d and then back to "b", but that cell is already used in this word.
"a" and "d" touch only at a corner, so "ad" can't be traced either.

Example 3:

Input: board = [
  ["s", "e", "e"],
  ["n", "e", "t"]
], words = ["see", "seen", "set", "net", "tee", "teen"]
Output: ["net", "see", "seen", "tee"]
Explanation: "see" can be traced in two ways (its last "e" is either to the right or below), but it is listed once.
"seen" goes s → e → e (the one below) → n, so the path of "see" is the start of the path of "seen".
"set" can't be traced: the only "e" next to "s" is not next to "t". Neither can "teen": in every path t → e → e, the second "e" is the top middle one, which is not next to "n".

 

Constraints:

  • 1 <= R, C <= 12
  • Every cell of board holds a lowercase English letter.
  • 1 <= words.length <= 3 * 104
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters, and all the words are different.

Note:

Searching the board once for every word repeats the same work for words that start the same way. Put the words in a trie instead, and search the board once: a depth-first search from each cell follows only the trie's paths. With words of at most L letters, each search goes at most L cells deep, so the time is O(R * C * 4L), plus the time to build the trie, whatever the number of words.

STEP 1 OF 25
    Ctrl + Enter to check

    JAVA · TRIES

    Word Search Ii in Java, explained

    Problem overview

    The method findWords receives a grid of letters, board (a char[][]), and an array of strings, words. It returns every word that can be traced on the board. A word is traced along a path of cells in which each cell touches the previous one horizontally or vertically, never diagonally, and no cell is used twice within one word. Each word that can be traced appears once in the result, in any order. The lesson's tests list the answer alphabetically.

    In the first example the board is

    o a a n
e t a e
i h k r
i f l v

    and the words are oath, pea, eat and rain. The answer is [eat, oath]. The word oath goes from the top-left o right to a, then down to t and down again to h. The board has no p, and no a touches the r, so pea and rain can't be traced.

    Approach: one search for all the words

    The direct way runs a depth-first search from every cell for every word. Many words share beginnings, so the same paths get walked again and again, once per word.

    A trie fixes that. It stores the words as a tree of letters, where all words with the same beginning share the same nodes. A search over the board can then walk the board and the trie together: from a cell, the next letter must be a child of the current trie node, and if it isn't, no word continues this way and the search stops at once. One search from a cell looks for every word at the same time, and it never explores a path that isn't the beginning of some word.

    Each search goes at most L cells deep, where L is the length of the longest word, and branches in at most four directions, so the work is O(R · C · 4^L) for a board of R rows and C columns, plus the time to build the trie. The number of words affects only the trie-building cost.

    Step by step

    1. Give TrieNode a children map, a Map<Character, TrieNode> starting as an empty HashMap. It maps each next letter to the child node. Map keys must be objects, so the key type is Character, and Java converts between char and Character by itself.
    2. Give it a String word field, starting as null. On the node where a word ends, it holds that word. Storing the word itself instead of a yes/no flag lets the search add it to the answer the moment it reaches the node.
    3. Create the trie's root in findWords. It stands for the empty beginning, so every word starts there.
    4. Insert each word. Loop over the words, start a node at the root, then loop over the word's characters.
    5. Walk down, creating as needed. If the current node has no child for the letter, put a new TrieNode under it. Then move to that child.
    6. Mark the end. After the last letter, set node.word to the word.
    7. Prepare the answer. Create the list found, an ArrayList. The helper adds to this one list.
    8. Start a search from every cell. Two nested loops over the rows and columns call dfs(board, row, col, root, found). A word can begin anywhere. Every row has the same length, so board[0].length is the number of columns.
    9. Return found.
    10. In dfs, stop outside the board. The calls for the four neighbours are made without checking them, so from an edge cell some of them land off the board. They return here.
    11. Read the cell's letter into a char named letter, because it's needed again at the end to restore the cell.
    12. Stop if no word continues with this letter. If node.children has no key letter, return. This check is what keeps the search small.
    13. Move down the trie to child, the node for the path so far plus this cell.
    14. Report a finished word. If child.word isn't null, the path spells that word: add it to found, then set child.word back to null. A word can often be traced along several paths, and once it is cleared the later paths find nothing to add, so each word is listed once.
    15. Mark the cell as used by writing '#' into it. No word contains '#', so a call that comes back to this cell stops at the children check. A path therefore uses each cell at most once.
    16. Search the four neighbours with child as the trie node: below, above, right, left. From now on the path includes this cell.
    17. Restore the cell by putting letter back. The cell is free again for other paths. Undoing the mark on the way out is what makes this backtracking.

    The solution in Java

    class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    String word = null;
}

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                if (!node.children.containsKey(c)) {
                    node.children.put(c, new TrieNode());
                }
                node = node.children.get(c);
            }
            node.word = word;
        }
        List<String> found = new ArrayList<>();
        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[0].length; col++) {
                dfs(board, row, col, root, found);
            }
        }
        return found;
    }

    void dfs(char[][] board, int row, int col, TrieNode node, List<String> found) {
        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length) {
            return;
        }
        char letter = board[row][col];
        if (!node.children.containsKey(letter)) {
            return;
        }
        TrieNode child = node.children.get(letter);
        if (child.word != null) {
            found.add(child.word);
            child.word = null;
        }
        board[row][col] = '#';
        dfs(board, row + 1, col, child, found);
        dfs(board, row - 1, col, child, found);
        dfs(board, row, col + 1, child, found);
        dfs(board, row, col - 1, child, found);
        board[row][col] = letter;
    }
}

    Java details worth a closer look:

    • A path through the trie, not just the board. dfs takes node, the trie node reached before the cell, and passes child down to its neighbours. The letter of the cell is looked up in node.children, and its result becomes the node for the next level.
    • Passing arrays and lists. Java passes the reference to board and to found, so changes made in dfs are visible to the caller. That is why writing '#' into a cell works without returning anything, and why the restore on the last line matters: the caller's board would otherwise stay damaged.
    • char keys. containsKey(c) and put(c, ...) box the char into a Character. Lookups work because Character implements equals and hashCode by value.
    • toCharArray(). It returns a new char[] with the characters of the string, which the for-each loop reads one at a time.
    • The order of the result. found is in the order the searches discover the words. On the first example it is [oath, eat], because the search meets the top-left o first. The tests list the answer alphabetically, so a solution should not rely on its own order.
    • The board is restored. After findWords returns, every cell holds its original letter again.

    Complexity

    Time: O(R · C · 4^L) for the search, plus O(W · L) to build the trie for W words. A search from one cell goes down at most L levels and tries four neighbours at each one, and it only continues while the letters match a path in the trie. In practice most searches stop after a step or two.

    Space: O(W · L) for the trie, since each word adds at most L nodes, plus O(L) for the recursion. The board is changed in place and restored, so it costs nothing extra.

    Edge cases and common mistakes

    • Reusing a cell. On [["a","b"],["c","d"]] the word abdb needs the cell with b twice and can't be traced. Without the '#' mark the search would accept it.
    • Diagonal neighbours. ad on that board is not traced, because a and d touch only at a corner.
    • Listing a word twice. On [["s","e","e"],["n","e","t"]] the word see can be traced in two ways, and the answer still has it once. That is the job of setting child.word to null.
    • Words that start other words. With see and seen in the list, the node for see reports its word and the search continues below it. Do not stop at the first word found along a path.
    • Forgetting to restore the cell. The cell stays '#' and later searches can't pass through it. Words are missed, and which ones depends on the order of the search.
    • Looking at a cell before the bounds check. Reading board[row][col] first throws ArrayIndexOutOfBoundsException for a neighbour off the board.
    • Single cells. A board with one letter and the word a gives [a], and the word aaa on [["a","a"]] gives an empty result, because only two cells exist.

    Testing

    • The board ["oaan","etae","ihkr","iflv"] (one string per row) with oath, pea, eat, rain gives [eat, oath] once sorted.
    • The board ["ab","cd"] with abdb, ad gives [].
    • The board ["see","net"] with see, seen, set, net, tee, teen gives [net, see, seen, tee] once sorted.
    • The board ["a"] with a gives [a].
    • The board ["aa"] with aaa gives [].
    • The board ["ab"] with ab, a, b, ba gives [a, ab, b, ba] once sorted.
    Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free