Start learning free

LESSON 426 OF 535 · TRIES

Word Search II in C++: Trie and Backtracking, O(R·C·4^L)

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

Given a grid of letters board with R rows and C columns, and a vector 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

    C++ · TRIES

    Word Search Ii in C++, explained

    Problem overview

    The method findWords receives a grid of letters, board, with R rows and C columns, and a vector of strings, words. It returns every word that can be traced on the board. A word is traced along 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 but not diagonally. A cell can be used only once within the same word. Each word is returned once, in any order, and the answer is empty when no word can be traced.

    In the first example, the board is

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

    and words = ["oath", "pea", "eat", "rain"]. The word "oath" starts at the top-left o, goes right to a, then down to t and down again to h. The word "eat" starts at the e at the end of the second row and goes left through a to t. The board has no p, and no a touches the r, so "pea" and "rain" are not found. The answer is eat and oath.

    Approach: search the board once, following a trie of the words

    The direct method is to run a path search on the board for every word. That repeats work: the words "oath" and "oat" both begin with the same three letters, and each search walks that start again. With up to 30,000 words, the repetition adds up.

    A trie (prefix tree) stores all the words at once. Each node stands for a prefix, and its children map each next letter to the node for the longer prefix. Words that start the same way share the same path from the root.

    The search uses the trie as a guide. From every cell, a depth-first search carries a trie node, the prefix traced so far. At each cell it asks whether the node has a child for the cell's letter. If it does not, no word continues this path, and the search stops immediately. If it does, the path moves one level down the trie, and the search continues into the four neighbours. One search from a cell looks for every word at once, and it only follows paths that begin some word.

    The search is backtracking: it marks a cell as used while the path goes through it, and undoes the mark when the path leaves the cell, so the cell is free again for other paths. With words of at most L letters, a path is at most L cells long and each step has at most four choices (usually three, since the path just came from one neighbour). That gives O(R · C · 4^L) time, plus the time to build the trie, whatever the number of words.

    Step by step

    The lesson first defines the trie node, then builds the trie in findWords, starts a search from each cell, and finally writes the search itself, dfs.

    1. Give TrieNode its children. An unordered_map<char, TrieNode*> named children maps each next letter to a pointer to the child node. It starts out empty.
    2. Store the finished word on the node. A string word = "" holds the whole word at the node where a word ends, and the empty string means that no word ends here. Every word has at least one letter, so "" can't be confused with a real word. Keeping the word itself instead of a flag lets the search put it in the answer the moment its path is complete.
    3. Create the root. TrieNode* root = new TrieNode() stands for the empty prefix.
    4. Insert each word. Loop over string& word : words.
    5. Start at the root. TrieNode* node = root is the walk's current position for this word.
    6. Loop over the letters with for (char c : word).
    7. Create a missing child. If !node->children.count(c), store a new TrieNode() in node->children[c].
    8. Move down: node = node->children[c]. The child exists now, whether it was already there or was just created.
    9. Mark the word's end. After the letter loop, set node->word = word.
    10. Prepare the answer. Declare vector<string> found. The helper adds to this one list, so searches from every cell collect into the same place.
    11. Loop over the rows, row from 0 while row < board.size().
    12. Loop over the columns, col from 0 while col < board[0].size(). Every row has the same length, so the first row gives the number of columns.
    13. Search from the cell: dfs(board, row, col, root, found). The board and the list are passed by reference, so the helper changes these, not copies.
    14. Return found. Each word is in it at most once, because the helper clears a word as soon as it finds it.
    15. Reject cells off the board. At the top of dfs, if row or col is below 0 or past the last row or column, return. The calls below step to all four neighbours without checking them first, so edge cells send some calls off the board, and they end here.
    16. Remember the letter. char letter = board[row][col] is needed again at the end, to put it back.
    17. Stop if no word continues. If !node->children.count(letter), return. This check keeps the search small.
    18. Go down the trie. TrieNode* child = node->children[letter] stands for the path so far plus this cell's letter.
    19. Check for a finished word. If child->word != "", the path spells exactly that word.
    20. Record it: found.push_back(child->word).
    21. Clear it: child->word = "". A word can often be traced along several paths. Once cleared, the next path that spells it adds nothing, so each word appears once.
    22. Mark the cell as used: board[row][col] = '#'. No word contains #, so a call that comes back to this cell stops at the children check.
    23. Search down and up: dfs with row + 1 and with row - 1, the same col, and child as the node. The path now includes this cell, so the neighbours continue from child.
    24. Search right and left: dfs with col + 1 and col - 1, the same row.
    25. Put the letter back: board[row][col] = letter. Undoing the mark when the search leaves a cell is what makes this backtracking.

    The solution in C++

    struct TrieNode {
    unordered_map<char, TrieNode*> children;
    string word = "";
};

class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        TrieNode* root = new TrieNode();
        for (string& word : words) {
            TrieNode* node = root;
            for (char c : word) {
                if (!node->children.count(c)) {
                    node->children[c] = new TrieNode();
                }
                node = node->children[c];
            }
            node->word = word;
        }
        vector<string> found;
        for (int row = 0; row < board.size(); row++) {
            for (int col = 0; col < board[0].size(); col++) {
                dfs(board, row, col, root, found);
            }
        }
        return found;
    }

    void dfs(vector<vector<char>>& board, int row, int col, TrieNode* node, vector<string>& found) {
        if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size()) {
            return;
        }
        char letter = board[row][col];
        if (!node->children.count(letter)) {
            return;
        }
        TrieNode* child = node->children[letter];
        if (child->word != "") {
            found.push_back(child->word);
            child->word = "";
        }
        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;
    }
};

    The C++ details worth a closer look:

    • Pointers in the map. children stores TrieNode* pointers, so each child is a separate node made with new that stays alive until it is deleted. The lesson never deletes the trie, so its memory is not returned after the call; a long-running program would delete the nodes.
    • count versus []. children.count(c) only asks whether the key exists, while children[c] inserts an empty entry (a null pointer) when the key is missing. That is why every [] read in this code comes after a count check or right after the insertion.
    • Signed and unsigned. board.size() is unsigned, and row >= board.size() converts row to unsigned. A negative row would become a huge number, which is why row < 0 comes first in the condition.
    • Reference parameters. vector<vector<char>>& board and vector<string>& found avoid copying the grid and the list on every recursive call. They also let dfs change the one shared board and add to the one shared answer.
    • The board is changed and restored. While a path is in progress, its cells hold #. When every call has returned, each cell has its original letter again, so the caller's board is left as it was.
    • Order of the answer. findWords returns words in the order the search finds them, not alphabetically: on the first example the order is oath, then eat. The problem accepts any order.

    Complexity

    Let the board have R rows and C columns, the longest word have L letters, and the total number of letters in all words be S.

    Time: O(S + R · C · 4^L). Building the trie takes one step per letter, O(S). Then dfs is started from R · C cells. A path can't be longer than the longest word, because the trie has no deeper node, so each search goes at most L cells deep with at most four choices per step. The number of words doesn't multiply this term: all the words share one search, and the trie check cuts every path that doesn't start a word.

    Space: O(S) for the trie in the worst case, when no two words share a prefix, plus O(L) for the recursion stack and the answer. The board is reused, not copied.

    Edge cases and common mistakes

    • A cell used twice. On the board [["a","b"],["c","d"]], "abdb" would need the b again, and "ad" needs a diagonal step. Neither is found, and the answer is empty. Marking cells with # is what prevents the reuse.
    • One word, several paths. On the board [["s","e","e"],["n","e","t"]], the word "see" can be traced in two ways. Without clearing child->word, the answer for the words ["see","seen","set","net","tee","teen"] would list "see" and "tee" twice: see, seen, see, net, tee, tee. With the clearing it is see, seen, net, tee.
    • Forgetting to restore the letter. If the last line of dfs is missing, cells stay as # after the first path that visited them, and later paths and later start cells fail. On the first example the answer would shrink to just oath.
    • Checking the neighbours before the board edge. Reading board[row][col] before the bounds test indexes outside the vector, which is undefined behaviour.
    • Prefix words. A word can be a prefix of another. With ["a","ab","b","ba"] on [["a","b"]], all four are found, because the word is recorded at the node where its path ends and the search continues deeper below it.
    • A word longer than the board allows. On [["a","a"]], the word "aaa" would need three cells, and the answer is empty.
    • Using a flag instead of the word. With a boolean flag on the node, the search would have to rebuild the word from the path. Storing the word itself is simpler.

    Testing

    Each answer below is shown sorted.

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