Start learning free

LESSON 351 OF 539 · 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 an array of rows, and each row is an array 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 char[][] (an array of rows, each row an array of letters), and a string word. It returns true when the word can be traced through the grid and false otherwise.

    To trace a word, start at any cell and move one step at a time up, down, left or right, never diagonally. The cells visited must spell the word in order, and no cell may be used twice. Letters are case-sensitive.

    Take this board:

    A B C E
S F C S
A D E E

    The word ABCCED is on the board: A at row 0, column 0, then B, then C along the top row, down to the C in row 1, down to the E in row 2, and left to D. The word SEE is there too, going down from the S in the right column. The word ABCB is not: A, B, C work along the top row, but the only B next to that C is the one already used.

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

    The word can start anywhere, so the method tries every cell as the first letter. From a start cell, a depth-first search matches one letter per call: if the cell holds the letter, the search asks the four neighbours to match the rest of the word. A path is abandoned at its first wrong letter, which keeps the search small in practice.

    The one subtle point is the rule that a cell can't be reused. The search marks a cell as used while it is on the current path. Once all four neighbours have been tried, the search unmarks the cell, because a different path, tried later, may legitimately pass through it. Marking, exploring and unmarking is what makes this backtracking.

    Rather than keeping a separate visited table, the solution overwrites the cell with '#'. The statement guarantees the board contains only letters, so '#' never equals a letter of word, and a marked cell fails the letter test automatically. The cell's real letter is word[index], which is how it gets restored.

    Step by step

    Exist: try every start

    1. Loop over rows with row from 0 while row < board.Length. For a jagged array, board.Length is the number of rows.
    2. Loop over columns inside it, up to board[0].Length, the length of the first row. Every row has the same length here.
    3. Call Dfs(board, word, row, col, 0) and return true if it succeeds. The last argument, 0, is the index of the first letter. One successful start is enough.
    4. Return false after both loops, since no start worked.

    Dfs: match one letter

    1. Declare Dfs as a public bool method taking the board, the word, row, col and index, the position in the word of the letter this cell must hold. It answers whether the word from index to the end can be traced starting here.
    2. If index == word.Length, return true. Every letter has been matched, so this cell doesn't matter. It may even be off the board, which is why this test comes before the bounds test.
    3. Return false when the cell is off the board: a row or column below 0 or past the last one. Neighbours of edge cells land here, so testing once in Dfs saves every caller from checking.
    4. Return false when board[row][col] isn't word[index]. A wrong letter and an already used cell (holding '#') both stop here.
    5. Mark the cell by setting it to '#'.
    6. Create found as false. The method can't return as soon as a neighbour succeeds, because the cell must be unmarked first.
    7. Describe the four moves in an int[][] named directions: {-1, 0} up, {1, 0} down, {0, -1} left, {0, 1} right. One loop then replaces four copies of the same call.
    8. Loop over directions with foreach (int[] d in directions), where d[0] is the row change and d[1] the column change.
    9. Update found with found || Dfs(...) on the neighbour, with index + 1 for the next letter. The || operator skips its right side once found is true, so no more neighbours are searched after a success.
    10. Unmark the cell after the loop by writing word[index] back into it.
    11. Return found.

    The solution in C#

    class Solution {
    public bool Exist(char[][] board, string word) {
        for (int row = 0; row < board.Length; row++) {
            for (int col = 0; col < board[0].Length; col++) {
                if (Dfs(board, word, row, col, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    public bool Dfs(char[][] board, string word, int row, int col, int index) {
        if (index == word.Length) {
            return true;
        }
        if (row < 0 || row >= board.Length || col < 0 || col >= board[0].Length) {
            return false;
        }
        if (board[row][col] != word[index]) {
            return false;
        }
        board[row][col] = '#';
        bool found = false;
        int[][] directions = new int[][] { new int[]{-1, 0}, new int[]{1, 0}, new int[]{0, -1}, new int[]{0, 1} };
        foreach (int[] d in directions) {
            found = found || Dfs(board, word, row + d[0], col + d[1], index + 1);
        }
        board[row][col] = word[index];
        return found;
    }
}

    The C# details worth knowing:

    • Jagged array. char[][] is an array of char[] rows, indexed board[row][col]. This is different from a rectangular char[,], which is indexed board[row, col] and measured with GetLength.
    • Characters compare by value. board[row][col] != word[index] compares two char values, and indexing a string gives a char. Single quotes make a char ('#'), double quotes a string.
    • Arrays are references. The board is changed in place during the search, and every recursive call sees the same array. Because each mark is undone, the board is exactly as it was when Exist returns, even when the answer is false.
    • Short-circuit evaluation. In found || Dfs(...), the call on the right runs only while found is false. Writing found |= Dfs(...) would run all four calls even after a success, which still gives the right answer but wastes work.
    • Order of the tests. The base case, the bounds test and the letter test must run in that order. Reading board[row][col] before the bounds test throws IndexOutOfRangeException at the edges.

    Complexity

    Let R and C be the board's dimensions and L the length of word.

    Time: O(R * C * 4^L) in the worst case. There are R * C starting cells. From each, a path has up to L letters, and each step has at most 4 neighbours (3 after the first, since the cell it came from is marked). In practice most paths stop at the first wrong letter, so the search is much faster than this bound.

    Space: O(L). There is one active call per matched letter, so the recursion is at most L calls deep. The marks live in the board itself, so there is no visited table.

    Edge cases and common mistakes

    • A one-cell board. With the board {"A"}, the word A is found and the word AA is not, because the single cell can't be used twice.
    • Reusing a cell. Forgetting to mark cells lets a path go back and forth between two cells that hold the same letter. In the board {"AA"}, the word AAA would wrongly succeed. With marking, it correctly returns false.
    • Forgetting to unmark. A cell left as '#' after a failed path blocks every later path through it, and valid words are missed. The board is also corrupted for the next call.
    • Returning early. Writing return Dfs(...) inside the loop for the first direction skips the other three directions and the unmarking.
    • Checking the base case after the bounds. On the last letter, the final recursive call may be off the board, and a bounds test first would turn a complete match into false.
    • Case. a and A are different letters, so the word a is not on the board above.

    Testing

    On the board {"ABCE", "SFCS", "ADEE"}:

    • ABCCED gives true.
    • SEE gives true.
    • ABCB gives false.
    • E gives true.
    • a gives false.

    After each of these calls, the board still reads ABCE, SFCS, ADEE.

    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free