Start learning free

LESSON 347 OF 535 · BACKTRACKING

Word Search in C++: Backtracking with Depth-First Search

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

Given a grid of letters board and a string word, return true if word can be traced in the grid, and false otherwise.

The grid is a vector of rows, and each row is a vector of letters, one letter per cell. Rows are numbered from 0, top to bottom, and columns from 0, left to right.

To trace a word, start at any cell and move, one letter at a time, to a cell side by side with the current one: up, down, left or right, never diagonally. The cells must spell word in order, and each cell can be used at most once. Letters are case-sensitive: a and A are different letters.

 

Example 1:

Input: board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
], word = "ABCCED"
Output: true
Explanation: Start at the A in row 0, column 0, and go right to B and C,
down to the C in row 1, down to the E in row 2, and left to D:
A (0,0) -> B (0,1) -> C (0,2) -> C (1,2) -> E (2,2) -> D (2,1)

Example 2:

Input: board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
], word = "SEE"
Output: true
Explanation: S (1,3) -> E (2,3) -> E (2,2)

Example 3:

Input: board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
], word = "ABCB"
Output: false
Explanation: A -> B -> C works along the top row, but the only B next to that C
is the one the path already used, and a cell can't be used twice.

 

Constraints:

  • board has 1 to 6 rows and 1 to 6 columns, and every row has the same number of cells.
  • 1 <= word.length <= 15
  • board and word contain only lowercase and uppercase English letters.

Note:

The tutorial uses backtracking: a depth-first search from every cell. One call checks one cell against one letter of word. If they match, it marks the cell as used, asks its four neighbours for the next letter, and then unmarks the cell, so that paths tried later can use it again. A path stops at its first wrong letter, which keeps the search small in practice.

In the worst case, the search from each of the R·C cells branches into 4 directions for each of the L letters of word (3 after the first, since the cell it came from is used): O(R·C·4L) time, where R and C are the numbers of rows and columns and L is the length of word. The extra space is O(L), one call per letter matched so far.

STEP 1 OF 15
    Ctrl + Enter to check

    C++ · BACKTRACKING

    Word Search in C++, explained

    Problem overview

    The method exist receives board, a vector<vector<char>> of letters, and a string word. It returns true if the word can be traced through the grid and false otherwise. A path may start in any cell and moves up, down, left or right, never diagonally. Each step must land on the next letter of the word, and no cell may be used twice in one path. Letters are case-sensitive.

    The board in the examples is:

    ABCE
SFCS
ADEE

    "ABCCED" is found by going right along the top row to A, B, C, then down to the C below, down to E, and left to D. "SEE" is found at the right edge: S, then the E under it, then the E to its left. "ABCB" is not found: the path A, B, C works, but the only B next to that C is the one already used.

    Approach: try every start, extend one letter at a time, undo

    The grid is small (at most 6 by 6) and the word is short (at most 15 letters), so a search that tries paths one after another is enough. The shape of the search is backtracking: a depth-first search that makes a choice, explores what follows, and then takes the choice back so that other paths can use the same cell.

    One call of dfs answers a small question: starting at this cell, can the letters of word from position index to the end be traced? The call checks that the cell holds word[index]. If it does, it marks the cell as used and asks each of the four neighbours the same question for index + 1. Before returning it puts the cell's letter back.

    The word may begin anywhere, so exist calls dfs from every cell with index 0 and returns true at the first success.

    The search stays small because a path stops at its first wrong letter. In the worst case the search from each of the R*C cells branches into four directions for each of the L letters (three after the first, since the cell just left is in use), so the bound is O(R*C*4^L), but real boards cut most branches after a letter or two.

    Step by step

    1. Loop over every row from 0 while row < board.size().
    2. Loop over every column inside it, up to board[0].size(). Every row has the same length, so the first row's length works for all.
    3. Start a search at (row, col) with index 0. If dfs returns true, return true: one successful start is enough.
    4. Return false after both loops, since no cell could start the word.
    5. Declare dfs with the board and word as references, the cell, and the index of the letter this cell must hold.
    6. Test success first: if index == word.size(), every letter has been matched, so return true. The cell that matched the last letter already did the work, and the current cell may even be off the board, which is why this test comes before the bounds test.
    7. Reject cells outside the board: a row or column below 0 or past the last one returns false. Neighbours of edge cells land here.
    8. Reject a wrong letter: if board[row][col] differs from word[index], return false. A cell already on the path holds '#', which is never a letter, so this test also rejects reused cells.
    9. Mark the cell by writing '#' into it.
    10. Prepare a bool found, starting false, and the four moves as pairs of (row change, column change): up, down, left, right.
    11. Try each move in a loop that unpacks the pair as auto [dr, dc], and combine the results into found with ||.
    12. Unmark the cell by writing word[index] back. This is the backtracking step.
    13. Return found. It is not returned earlier, because the cell must be restored before the call ends.

    The solution in C++

    class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for (int row = 0; row < board.size(); row++) {
            for (int col = 0; col < board[0].size(); col++) {
                if (dfs(board, word, row, col, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& board, string& word, int row, int col, int index) {
        if (index == word.size()) {
            return true;
        }
        if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size()) {
            return false;
        }
        if (board[row][col] != word[index]) {
            return false;
        }
        board[row][col] = '#';
        bool found = false;
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (auto [dr, dc] : directions) {
            found = found || dfs(board, word, row + dr, col + dc, index + 1);
        }
        board[row][col] = word[index];
        return found;
    }
};

    C++ details worth a closer look:

    • References are essential for the board. dfs takes vector<vector<char>>&, so every call marks and unmarks the one shared board. A by-value board would be copied at every call, which is slow, and the marks would not be seen by the callers.
    • Short-circuit ||. In found || dfs(...), the right side runs only while found is still false. Once one neighbour completes the word, the other neighbours are skipped.
    • Structured bindings. auto [dr, dc] splits each pair<int, int> into two names. It needs C++17, which the lessons use.
    • Order inside the class. exist calls dfs before dfs is written. Inside a class body that is fine: member functions can use each other whatever the order.
    • Signed and unsigned. board.size() is unsigned. Comparing row >= board.size() converts row to unsigned, and a negative row would become a huge number, so this particular test would still reject it. The explicit row < 0 keeps the intent obvious. Compilers may warn about comparing signed and unsigned values.
    • The '#' marker. It works because the board holds only English letters. A board that could contain '#' would need a separate visited array.

    Complexity

    Time: O(R*C*4^L) in the worst case, with R rows, C columns and a word of L letters. There are R*C starting cells, and a path of L letters branches at most four ways per step (three after the first). Matching stops at the first wrong letter, so most inputs do much less work.

    Space: O(L) besides the board. The recursion is at most L calls deep, one per matched letter. The marks are written into the board itself, so no visited array is needed.

    Edge cases and common mistakes

    • Forgetting to unmark. Without the restore step, cells stay as '#' after a failed path, and later paths cannot use them. A word that needs one of those cells is wrongly reported as missing. With the restore step, the board is unchanged after exist returns.
    • Checking bounds after reading the cell. board[row][col] with row = -1 or col past the end is undefined behaviour. The bounds test has to come first.
    • Testing the index after the bounds. When the last letter matches at a cell on the edge, the next call is made on a neighbour that may be outside the board. If the bounds test came before the index == word.size() test, a word ending on the edge would be rejected.
    • Reusing a cell. Without the '#' mark, "ABCB" would be found by going A, B, C and back to the first B.
    • Diagonal moves. Only the four directions in directions are allowed.
    • A word longer than the board. A 1 by 1 board with "aa" gives false, because the only cell would be used twice.
    • Case. a and A are different letters, and the comparison is a plain != on char.

    Testing

    With the board above:

    • "ABCCED" gives true.
    • "SEE" gives true.
    • "ABCB" gives false.
    • "a" gives false, since the board has only capital letters.
    • "ASADFBCCEESE" gives true (a path that uses every one of the 12 cells).

    On other boards:

    • A board with the single cell a and the word "a" gives true, while the word "aa" gives false.
    • A board with one row, a b, and the word "ba" gives true, while "aba" gives false.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free