Skip to main content
CodePeetCodePeet
CodePeet 150

Word Search

MEDIUMProblemSolveExternal Links

Description

You are given an m × n grid of characters called board and a string word.

Return true if the word can be found in the grid by following a path of sequentially adjacent cells. Two cells are adjacent if they share a horizontal or vertical border (up, down, left, right — no diagonals).

Each cell may be used at most once in the path that forms the word. In other words, once you step on a cell to match a character, you cannot step on it again for the same word search.

Examples

Example 1

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

Output: true

Explanation: Starting at cell (0,0)='A', we move right to (0,1)='B', right to (0,2)='C', down to (1,2)='C', down to (2,2)='E', left to (2,1)='D'. This spells out "ABCCED", matching the word exactly. Each cell was used only once.

Example 2

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"

Output: true

Explanation: Starting at cell (1,3)='S', we move down to (2,3)='E', then left to (2,2)='E'. This spells "SEE". The path is valid because each cell is visited only once.

Example 3

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"

Output: false

Explanation: We can find A→B→C starting from (0,0)→(0,1)→(0,2), but the next character needed is 'B'. The only 'B' adjacent to (0,2) is (0,1), which was already used. No valid path exists that spells "ABCB" without reusing a cell.

Constraints

  • m == board.length
  • n == board[i].length
  • 1 ≤ m, n ≤ 6
  • 1 ≤ word.length ≤ 15
  • board and word consist of only lowercase and uppercase English letters

Editorial

Brute Force

Intuition

The most straightforward way to think about this problem is to consider every possible path in the grid.

For each cell in the grid, ask: "Can the word start here?" If the first character matches, try to extend the path to a neighboring cell that matches the second character, then from there try to extend to the third character, and so on. At each step, you have up to 4 neighboring cells to explore (up, down, left, right).

This is essentially a depth-first search (DFS) from every cell. You try all possible paths, and if any path spells out the full word, you return true.

Think of it like navigating a maze: you stand on a letter, check if it matches what you need, then try each corridor (neighbor). If you hit a dead end (wrong letter or out of bounds), you back up and try another corridor.

The brute force version of this approach does not optimize for early termination — it exhaustively tries all paths. We will call this the brute force because it represents the most naive exploration strategy before we add pruning.

Step-by-Step Explanation

Let's trace with board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE":

Step 1: Scan the grid for cells matching word[0] = 'S'. We find 'S' at (0,3)? No, (0,3)='E'. Let's check systematically: (0,0)='A', (0,1)='B', (0,2)='C', (0,3)='E', (1,0)='S' — match!

Step 2: Start DFS from (1,0)='S'. Mark (1,0) as visited. We need word[1]='E'. Check neighbors:

  • Up: (0,0)='A' ≠ 'E'. Skip.
  • Down: (2,0)='A' ≠ 'E'. Skip.
  • Left: out of bounds. Skip.
  • Right: (1,1)='F' ≠ 'E'. Skip.
    All neighbors fail. Unmark (1,0). This starting cell does not lead to a solution.

Step 3: Continue scanning. Next 'S' found at (1,3). Start DFS from (1,3)='S'. Mark (1,3) as visited. Need word[1]='E'.

  • Up: (0,3)='E' — match!

Step 4: Move to (0,3)='E'. Mark (0,3) as visited. Need word[2]='E'.

  • Up: out of bounds. Skip.
  • Down: (1,3)='S' — already visited. Skip.
  • Left: (0,2)='C' ≠ 'E'. Skip.
  • Right: out of bounds. Skip.
    All neighbors fail for the second 'E'. Unmark (0,3). Backtrack to (1,3).

Step 5: Back at (1,3). Try next neighbor for 'E':

  • Down: (2,3)='E' — match!

Step 6: Move to (2,3)='E'. Mark (2,3) as visited. Need word[2]='E'.

  • Up: (1,3)='S' — already visited. Skip.
  • Down: out of bounds. Skip.
  • Left: (2,2)='E' — match!

Step 7: Move to (2,2)='E'. Mark (2,2) as visited. We have matched all characters: S→E→E. Word found! Return true.

Brute Force DFS — Searching All Paths for "SEE" — Watch how we try each starting cell matching 'S', explore all neighbor paths via DFS, backtrack on failures, and eventually find a valid path spelling 'SEE'.

Algorithm

  1. For each cell (r, c) in the grid:
    • If board[r][c] matches word[0], start a DFS from (r, c)
  2. DFS(r, c, index):
    • If index equals word.length, all characters matched → return true
    • If (r, c) is out of bounds, or board[r][c] ≠ word[index], or cell is already visited → return false
    • Mark (r, c) as visited
    • Recursively call DFS on all 4 neighbors (up, down, left, right) with index + 1
    • If any recursive call returns true, propagate true upward
    • Otherwise, unmark (r, c) (backtrack) and return false
  3. If no starting cell leads to a complete match, return false

Code

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size(), n = board[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
private:
    bool dfs(vector<vector<char>>& board, string& word, int r, int c, int idx) {
        if (idx == word.size()) return true;
        if (r < 0 || r >= board.size() || c < 0 || c >= board[0].size())
            return false;
        if (board[r][c] != word[idx]) return false;
        
        char temp = board[r][c];
        board[r][c] = '#';  // mark visited
        
        bool found = dfs(board, word, r + 1, c, idx + 1)
                  || dfs(board, word, r - 1, c, idx + 1)
                  || dfs(board, word, r, c + 1, idx + 1)
                  || dfs(board, word, r, c - 1, idx + 1);
        
        board[r][c] = temp;  // unmark (backtrack)
        return found;
    }
};
class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        
        def dfs(r: int, c: int, idx: int) -> bool:
            if idx == len(word):
                return True
            if r < 0 or r >= m or c < 0 or c >= n:
                return False
            if board[r][c] != word[idx]:
                return False
            
            temp = board[r][c]
            board[r][c] = '#'  # mark visited
            
            found = (dfs(r + 1, c, idx + 1) or
                     dfs(r - 1, c, idx + 1) or
                     dfs(r, c + 1, idx + 1) or
                     dfs(r, c - 1, idx + 1))
            
            board[r][c] = temp  # unmark (backtrack)
            return found
        
        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False
class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board, String word, int r, int c, int idx) {
        if (idx == word.length()) return true;
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length)
            return false;
        if (board[r][c] != word.charAt(idx)) return false;
        
        char temp = board[r][c];
        board[r][c] = '#';  // mark visited
        
        boolean found = dfs(board, word, r + 1, c, idx + 1)
                     || dfs(board, word, r - 1, c, idx + 1)
                     || dfs(board, word, r, c + 1, idx + 1)
                     || dfs(board, word, r, c - 1, idx + 1);
        
        board[r][c] = temp;  // unmark (backtrack)
        return found;
    }
}

Complexity Analysis

Time Complexity: O(m × n × 4^L)

We try starting the DFS from each of the m × n cells. From each cell, the DFS explores up to 4 directions at each of the L characters in the word (where L = word.length). In the worst case, this gives us 4^L paths per starting cell. Therefore, the worst-case time is O(m × n × 4^L). In practice, many paths are pruned early because characters do not match.

Space Complexity: O(L)

The recursion depth is at most L (the length of the word), since we go one level deeper for each character matched. We also temporarily modify the board in place (marking cells with '#'), which requires no extra space beyond the recursion stack.

Why This Approach Is Not Efficient

The brute force DFS explores all 4 directions at every step without any optimization. With a word of length L, the search tree has up to 4^L nodes per starting cell. Even for modest values of L (say 15), 4^15 ≈ 1 billion — an enormous number of paths.

The fundamental issue is that we explore clearly hopeless paths. For example, if the word starts with 'Z' but there is no 'Z' in the grid, we still iterate over every cell. If the word contains 5 copies of a letter that appears only once in the grid, we waste time exploring paths that will inevitably fail.

Key insights for improvement:

  1. Character frequency pruning: Before starting, check if the grid contains enough of each character the word needs. If the word requires 3 'A's but the grid has only 2, return false immediately.
  2. Reverse word trick: If the last character of the word appears fewer times in the grid than the first character, search for the reversed word instead — this reduces the number of starting cells.
  3. Short-circuit evaluation: In the DFS, as soon as one direction succeeds, skip the remaining directions (using || short-circuiting).

These optimizations do not change the worst-case complexity, but they dramatically reduce the practical runtime by pruning the search space.

Optimal Approach - Backtracking with Pruning

Intuition

The optimal approach uses the same DFS backtracking framework but adds intelligent pruning to eliminate impossible paths before exploring them.

Think of the grid as a maze and the word as a secret combination. Before entering the maze, you first check: "Does this maze even contain all the letters I need?" If the answer is no, you walk away immediately. If yes, you choose the entrance that gives you the fewest starting options — reducing the total number of paths to explore.

Specifically, the optimizations are:

  1. Character count validation: Count each character in the grid and in the word. If any character in the word appears more times than it does in the grid, the word cannot possibly be formed — return false without any DFS.

  2. Reverse search optimization: Count how many cells match the first character of the word and how many match the last character. If the last character has fewer matches, reverse the word before searching. This means fewer starting cells, leading to fewer DFS calls overall.

  3. In-place visited marking: Instead of maintaining a separate visited matrix, temporarily replace the current cell's value with a sentinel character (like '#'). This saves space and time compared to a separate data structure. After backtracking, restore the original character.

  4. Short-circuit in DFS: Use logical OR (||) so that as soon as one direction finds the word, the remaining directions are not explored.

These pruning strategies work together to cut the practical search space significantly while using the same elegant backtracking structure.

Step-by-Step Explanation

Let's trace with board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED":

Step 1: Pre-check character counts.

  • Word needs: A=1, B=1, C=2, E=1, D=1.
  • Grid has: A=2, B=1, C=2, E=3, S=2, F=1, D=1.
  • Every character in the word has sufficient count in the grid. Proceed.

Step 2: Reverse check.

  • word[0]='A' appears 2 times in grid. word[5]='D' appears 1 time.
  • Last char has fewer occurrences (1 < 2), so reverse the word: search for "DECCBA" instead.
  • (For clarity, let's trace the original direction here, but in practice, reversing reduces starts.)

Step 3: Scan for word[0]='A'. Found at (0,0). Start DFS.

Step 4: At (0,0)='A', matches word[0]. Mark as '#'. Need word[1]='B'.

  • Right neighbor (0,1)='B' — match!

Step 5: At (0,1)='B', matches word[1]. Mark as '#'. Need word[2]='C'.

  • Right neighbor (0,2)='C' — match!

Step 6: At (0,2)='C', matches word[2]. Mark as '#'. Need word[3]='C'.

  • Down neighbor (1,2)='C' — match!

Step 7: At (1,2)='C', matches word[3]. Mark as '#'. Need word[4]='E'.

  • Down neighbor (2,2)='E' — match!

Step 8: At (2,2)='E', matches word[4]. Mark as '#'. Need word[5]='D'.

  • Left neighbor (2,1)='D' — match!

Step 9: At (2,1)='D', matches word[5]. index == word.length. All characters matched!

Step 10: Return true. The path (0,0)→(0,1)→(0,2)→(1,2)→(2,2)→(2,1) spells "ABCCED".

Backtracking with Pruning — Finding "ABCCED" — Watch the DFS trace the path A→B→C→C→E→D through the grid. Each cell is marked as visited to prevent reuse, and the path grows step by step until the full word is matched.

Algorithm

  1. Pre-check (pruning): Count characters in the grid and in the word. If any character in the word has a higher count than in the grid, return false immediately.
  2. Reverse optimization: Count occurrences of word[0] and word[last] in the grid. If word[last] occurs fewer times, reverse the word (search for the reversed word instead — this reduces starting cells).
  3. Search: For each cell (r, c) in the grid:
    • If board[r][c] == word[0], call DFS(r, c, 0)
    • If DFS returns true, return true
  4. DFS(r, c, index):
    • If index == word.length, return true (all characters matched)
    • If (r, c) is out of bounds, or board[r][c] ≠ word[index], return false
    • Save board[r][c], replace it with '#' (mark visited)
    • Recursively try all 4 directions with index + 1, using || for short-circuit
    • Restore board[r][c] (backtrack)
    • Return the result
  5. If no starting cell succeeds, return false

Code

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size(), n = board[0].size();
        
        // Pruning: check character counts
        unordered_map<char, int> gridCount;
        for (auto& row : board)
            for (char c : row)
                gridCount[c]++;
        
        unordered_map<char, int> wordCount;
        for (char c : word)
            wordCount[c]++;
        
        for (auto& [ch, cnt] : wordCount) {
            if (gridCount[ch] < cnt) return false;
        }
        
        // Reverse optimization: start from rarer end
        if (gridCount[word.back()] < gridCount[word.front()]) {
            reverse(word.begin(), word.end());
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
private:
    bool dfs(vector<vector<char>>& board, string& word, int r, int c, int idx) {
        if (idx == (int)word.size()) return true;
        if (r < 0 || r >= (int)board.size() || c < 0 || c >= (int)board[0].size())
            return false;
        if (board[r][c] != word[idx]) return false;
        
        char temp = board[r][c];
        board[r][c] = '#';
        
        bool found = dfs(board, word, r + 1, c, idx + 1)
                  || dfs(board, word, r - 1, c, idx + 1)
                  || dfs(board, word, r, c + 1, idx + 1)
                  || dfs(board, word, r, c - 1, idx + 1);
        
        board[r][c] = temp;
        return found;
    }
};
class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        
        # Pruning: check character counts
        from collections import Counter
        grid_count = Counter()
        for row in board:
            for ch in row:
                grid_count[ch] += 1
        
        word_count = Counter(word)
        for ch, cnt in word_count.items():
            if grid_count[ch] < cnt:
                return False
        
        # Reverse optimization: start from rarer end
        if grid_count[word[-1]] < grid_count[word[0]]:
            word = word[::-1]
        
        def dfs(r: int, c: int, idx: int) -> bool:
            if idx == len(word):
                return True
            if r < 0 or r >= m or c < 0 or c >= n:
                return False
            if board[r][c] != word[idx]:
                return False
            
            temp = board[r][c]
            board[r][c] = '#'
            
            found = (dfs(r + 1, c, idx + 1) or
                     dfs(r - 1, c, idx + 1) or
                     dfs(r, c + 1, idx + 1) or
                     dfs(r, c - 1, idx + 1))
            
            board[r][c] = temp
            return found
        
        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False
class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        
        // Pruning: check character counts
        int[] gridCount = new int[128];
        for (char[] row : board)
            for (char c : row)
                gridCount[c]++;
        
        int[] wordCount = new int[128];
        for (char c : word.toCharArray())
            wordCount[c]++;
        
        for (int i = 0; i < 128; i++) {
            if (wordCount[i] > gridCount[i]) return false;
        }
        
        // Reverse optimization
        char[] w = word.toCharArray();
        if (gridCount[w[w.length - 1]] < gridCount[w[0]]) {
            for (int i = 0; i < w.length / 2; i++) {
                char tmp = w[i];
                w[i] = w[w.length - 1 - i];
                w[w.length - 1 - i] = tmp;
            }
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, w, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board, char[] word, int r, int c, int idx) {
        if (idx == word.length) return true;
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length)
            return false;
        if (board[r][c] != word[idx]) return false;
        
        char temp = board[r][c];
        board[r][c] = '#';
        
        boolean found = dfs(board, word, r + 1, c, idx + 1)
                     || dfs(board, word, r - 1, c, idx + 1)
                     || dfs(board, word, r, c + 1, idx + 1)
                     || dfs(board, word, r, c - 1, idx + 1);
        
        board[r][c] = temp;
        return found;
    }
}

Complexity Analysis

Time Complexity: O(m × n × 3^L)

We try each of the m × n cells as a starting point. From each cell, at each recursion level we explore at most 3 new directions (not 4, because we cannot go back to the cell we just came from — it is marked as visited). With L characters in the word, this gives up to 3^L paths per starting cell. The character-count pruning and reverse optimization further reduce this in practice, but the worst-case bound is O(m × n × 3^L).

Space Complexity: O(L)

The recursion stack goes at most L levels deep (one level per character in the word). We modify the board in-place with a sentinel character to track visited cells, avoiding the need for a separate visited matrix. So extra space is O(L) for the call stack.