# Word Search
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/word-search)
Canonical: https://scaleengineer.com/dsa/problems/word-search
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Array, String, Matrix
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Atlassian](https://scaleengineer.com/companies/atlassian), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Cisco](https://scaleengineer.com/companies/cisco), [Epic Systems](https://scaleengineer.com/companies/epic-systems), [FreshWorks](https://scaleengineer.com/companies/freshworks), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Karat](https://scaleengineer.com/companies/karat), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [Paytm](https://scaleengineer.com/companies/paytm), [Samsung](https://scaleengineer.com/companies/samsung), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wix](https://scaleengineer.com/companies/wix), [Zoho](https://scaleengineer.com/companies/zoho), [tcs](https://scaleengineer.com/companies/tcs), [Capital One](https://scaleengineer.com/companies/capital-one), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [Netflix](https://scaleengineer.com/companies/netflix), [Citadel](https://scaleengineer.com/companies/citadel), [Snap](https://scaleengineer.com/companies/snap), [Zepto](https://scaleengineer.com/companies/zepto), [Arista Networks](https://scaleengineer.com/companies/arista-networks), [Grammarly](https://scaleengineer.com/companies/grammarly), [Faire](https://scaleengineer.com/companies/faire), [Whatnot](https://scaleengineer.com/companies/whatnot)
---
## Problem
Given an `m x n` grid of characters `board` and a string `word`, return `true` _if_ `word` _exists in the grid_.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

**Example 1:**

![](https://assets.glich.co/dsa/word-search/image0.jpg) 

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

**Example 2:**

![](https://assets.glich.co/dsa/word-search/image1.jpg) 

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

**Example 3:**

![](https://assets.glich.co/dsa/word-search/image2.jpg) 

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

**Constraints:**

* `m == board.length`
* `n = board[i].length`
* `1 <= m, n <= 6`
* `1 <= word.length <= 15`
* `board` and `word` consists of only lowercase and uppercase English letters.

**Follow up:** Could you use search pruning to make your solution faster with a larger `board`?

# Approaches
## Backtracking with Depth-First Search (DFS)
This approach treats the 2D grid as a graph where adjacent cells are connected. The problem then becomes finding a path in this graph that spells out the given word. We can use Depth-First Search (DFS) combined with backtracking to explore all possible paths starting from each cell.
**Time:** O(N * M * 3^L), where N and M are the dimensions of the board, and L is the length of the word. We iterate through N * M cells. The DFS from each cell can go up to L levels deep. At each level (except the first), there are at most 3 directions to explore. · **Space:** O(L), where L is the length of the word. This space is used by the recursion stack.
**Pros:** Conceptually straightforward, applying a standard graph traversal algorithm.; Correctly handles the constraint of not reusing cells via backtracking.; Sufficiently efficient for the given problem constraints.
**Cons:** The time complexity is exponential in the length of the word, which can be slow for larger inputs.; May perform unnecessary searches if the starting character of the word is very common on the board.
### Explanation
The core of the solution is a recursive DFS function that explores paths. We iterate through every cell of the board. If a cell's character matches the first character of the word, we initiate a DFS from that cell. 

The DFS function, let's call it `search(row, col, index)`, tries to find the rest of the word starting from `word.charAt(index)` at the grid position `(row, col)`. 

To prevent using the same letter cell more than once in a single path, we mark the current cell as visited before exploring its neighbors. A common technique is to temporarily modify the character in the board at the current position (e.g., to '#'). After the recursive calls for its neighbors return, we must backtrack by restoring the cell's original character. This ensures the cell is available for other paths that might start from a different initial cell. 

The search proceeds in 4 directions (up, down, left, right). If any of these recursive searches find the complete word, we return `true`. If all paths from a starting cell are exhausted without finding the word, we continue the search from the next potential starting cell in the grid.

Here is the implementation in Java:
```java
class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // Start search only if the first character matches
                if (board[i][j] == word.charAt(0) && dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int r, int c, int index) {
        // Base case: Successfully found the entire word
        if (index == word.length()) {
            return true;
        }

        // Boundary checks and character match check
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != word.charAt(index)) {
            return false;
        }

        // Mark the current cell as visited to avoid using it again in the same path
        char temp = board[r][c];
        board[r][c] = '#'; 

        // Explore all 4 adjacent cells
        boolean found = dfs(board, word, r + 1, c, index + 1) ||
                        dfs(board, word, r - 1, c, index + 1) ||
                        dfs(board, word, r, c + 1, index + 1) ||
                        dfs(board, word, r, c - 1, index + 1);

        // Backtrack: Restore the cell's original character
        board[r][c] = temp;

        return found;
    }
}
```
### Algorithm
- Iterate through each cell `(i, j)` in the `board`.
- If `board[i][j]` matches the first character of `word`, call a recursive helper function `dfs(i, j, 0)` to start the search.
- If the helper function returns `true`, the word is found, so return `true` immediately.
- If the loops complete without finding the word, return `false`.
- **Inside the `dfs(row, col, index)` function:**
  - **Base Case 1:** If `index` equals `word.length()`, it means we have successfully matched all characters. Return `true`.
  - **Base Case 2:** If the current coordinates `(row, col)` are out of the board's bounds, or if `board[row][col]` does not match `word.charAt(index)`, this path is invalid. Return `false`.
  - **Recursive Step:**
    - a. Mark the current cell as visited to avoid cycles. For example, `char temp = board[row][col]; board[row][col] = '#';`
    - b. Explore the four adjacent neighbors (up, down, left, right) by calling `dfs` for each with `index + 1`.
    - c. If any of the four recursive calls return `true`, set a `found` flag to `true`.
  - **Backtrack:**
    - a. Restore the original character of the cell: `board[row][col] = temp;`
    - b. Return the `found` flag.

## Optimized Backtracking with Search Pruning
This approach enhances the standard backtracking algorithm by incorporating pruning techniques. Pruning helps to eliminate non-viable search paths early, which can significantly improve performance in practice, especially on larger boards or when there's a clear mismatch between the word's character requirements and the board's character availability.
**Time:** O(N * M * 3^L). The worst-case asymptotic complexity remains the same as the basic approach because the pruning steps might not eliminate any paths in some cases. However, the practical runtime is often much better. · **Space:** O(L + k), where L is the word length (for recursion) and k is the alphabet size (for frequency counts). Since k is constant, this simplifies to O(L).
**Pros:** More efficient in practice by avoiding searches that are guaranteed to fail.; The pruning logic is relatively cheap to compute compared to the cost of the search itself.; Reduces the number of starting points for the DFS, which is a major performance bottleneck.
**Cons:** The added complexity of the pruning logic can make the code slightly harder to read and implement.; The effectiveness of the pruning depends on the specific board and word provided.
### Explanation
Before starting the expensive DFS traversal, we can perform a few quick checks to see if a solution is even possible. 

First, a simple check: if the length of the `word` is greater than the total number of cells in the `board`, it's impossible to form the word, so we can return `false` immediately. 

Second, a more powerful check involves character frequencies. We can count the occurrences of each character required by the `word` and compare them against the character counts on the `board`. If the board doesn't have enough of a specific character needed for the word, we can again return `false` without any searching. 

Finally, we can add a heuristic to guide the search. The number of starting points for our DFS is determined by the number of occurrences of the first character of the word. If the last character of the word is rarer on the board than the first character, it's more efficient to search for the word in reverse. This reduces the number of top-level DFS calls. After these pruning steps, we proceed with the same DFS and backtracking logic as the basic approach.

Here is an implementation that includes these pruning steps:
```java
class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;

        // Pruning 1: Word length
        if (word.length() > m * n) {
            return false;
        }

        // Pruning 2 & 3 setup: Count character frequencies on the board
        int[] boardCounts = new int[128]; // Assuming ASCII characters
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                boardCounts[board[i][j]]++;
            }
        }

        // Pruning 2: Check if board has enough characters for the word
        int[] wordCounts = new int[128];
        for (char c : word.toCharArray()) {
            wordCounts[c]++;
        }
        for (int i = 0; i < 128; i++) {
            if (wordCounts[i] > boardCounts[i]) {
                return false;
            }
        }

        // Pruning 3: Search from the rarer end of the word
        if (boardCounts[word.charAt(0)] > boardCounts[word.charAt(word.length() - 1)]) {
            word = new StringBuilder(word).reverse().toString();
        }

        // Main DFS loop
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word.charAt(0) && dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int r, int c, int index) {
        if (index == word.length()) return true;
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != word.charAt(index)) return false;
        
        char temp = board[r][c];
        board[r][c] = '#'; // Mark as visited
        
        boolean found = dfs(board, word, r + 1, c, index + 1) ||
                        dfs(board, word, r - 1, c, index + 1) ||
                        dfs(board, word, r, c + 1, index + 1) ||
                        dfs(board, word, r, c - 1, index + 1);
        
        board[r][c] = temp; // Backtrack
        return found;
    }
}
```
### Algorithm
- **Pruning Step 1:** If `word.length() > m * n`, return `false`.
- **Pruning Step 2:** Count character frequencies on the `board` and in the `word`. If `count_board(c) < count_word(c)` for any character `c`, return `false`.
- **Pruning Step 3 (Heuristic):** Compare the frequency of the first and last characters of the `word` on the board. If the last character is less frequent, reverse the `word` to reduce the number of search starting points.
- **Main Search:** Proceed with the same DFS backtracking algorithm as the previous approach, iterating through the board to find starting cells that match the (potentially reversed) word's first character.

# Solutions
### CSharp

```csharp
public class Solution {
    private int m;
    private int n;
    private char[][] board;
    private string word;
    public bool Exist(char[][] board, string word) {
        m = board.Length;
        n = board[0].Length;
        this.board = board;
        this.word = word;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dfs(i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    private bool dfs(int i, int j, int k) {
        if (k == word.Length - 1) {
            return board[i][j] == word[k];
        }
        if (board[i][j] != word[k]) {
            return false;
        }
        char c = board[i][j];
        board[i][j] = '0';
        int[] dirs = {
            -1,
            0,
            1,
            0,
            -1
        };
        for (int u = 0; u < 4; ++u) {
            int x = i + dirs[u];
            int y = j + dirs[u + 1];
            if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] != '0' && dfs(x, y, k + 1)) {
                return true;
            }
        }
        board[i][j] = c;
        return false;
    }
}
```

### Java

```java
class Solution {
private
  int m;
private
  int n;
private
  String word;
private
  char[][] board;
public
  boolean exist(char[][] board, String word) {
    m = board.length;
    n = board[0].length;
    this.word = word;
    this.board = board;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (dfs(i, j, 0)) {
          return true;
        }
      }
    }
    return false;
  }
private
  boolean dfs(int i, int j, int k) {
    if (k == word.length() - 1) {
      return board[i][j] == word.charAt(k);
    }
    if (board[i][j] != word.charAt(k)) {
      return false;
    }
    char c = board[i][j];
    board[i][j] = '0';
    int[] dirs = {-1, 0, 1, 0, -1};
    for (int u = 0; u < 4; ++u) {
      int x = i + dirs[u], y = j + dirs[u + 1];
      if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] != '0' &&
          dfs(x, y, k + 1)) {
        return true;
      }
    }
    board[i][j] = c;
    return false;
  }
}

```

### JavaScript

```javascript
function exist ( board , word ) { const [ m , n ] = [ board . length , board [ 0 ]. length ]; const dirs = [ - 1 , 0 , 1 , 0 , - 1 ]; const dfs = ( i , j , k ) => { if ( k === word . length - 1 ) { return board [ i ][ j ] === word [ k ]; } if ( board [ i ][ j ] !== word [ k ]) { return false ; } const c = board [ i ][ j ]; board [ i ][ j ] = ' 0 ' ; for ( let u = 0 ; u < 4 ; ++ u ) { const [ x , y ] = [ i + dirs [ u ], j + dirs [ u + 1 ]]; const ok = x >= 0 && x < m && y >= 0 && y < n ; if ( ok && board [ x ][ y ] !== ' 0 ' && dfs ( x , y , k + 1 )) { return true ; } } board [ i ][ j ] = c ; return false ; }; for ( let i = 0 ; i < m ; ++ i ) { for ( let j = 0 ; j < n ; ++ j ) { if ( dfs ( i , j , 0 )) { return true ; } } } return false ; }
```

### CPP

```cpp
class Solution {
public:
  bool exist(vector<vector<char>> &board, string word) {
    int m = board.size(), n = board[0].size();
    int dirs[5] = {-1, 0, 1, 0, -1};
    function<bool(int, int, int)> dfs = [&](int i, int j, int k) -> bool {
      if (k == word.size() - 1) {
        return board[i][j] == word[k];
      }
      if (board[i][j] != word[k]) {
        return false;
      }
      char c = board[i][j];
      board[i][j] = '0';
      for (int u = 0; u < 4; ++u) {
        int x = i + dirs[u], y = j + dirs[u + 1];
        if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] != '0' &&
            dfs(x, y, k + 1)) {
          return true;
        }
      }
      board[i][j] = c;
      return false;
    };
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (dfs(i, j, 0)) {
          return true;
        }
      }
    }
    return false;
  }
};

```

### Python

```python
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool: def dfs(i, j, cur):  # cur: current char count if cur == len ( word ): return True if ( i < 0 or i >= m or j < 0 or j >= n or board [ i ][ j ] == '0' or word [ cur ] != board [ i ][ j ] ): return False t = board [ i ][ j ] board [ i ][ j ] = '0' # mark as visited for a , b in [[ 0 , 1 ], [ 0 , - 1 ], [ - 1 , 0 ], [ 1 , 0 ]]: x , y = i + a , j + b if dfs ( x , y , cur + 1 ): return True board [ i ][ j ] = t return False m , n = len ( board ), len ( board [ 0 ]) return any ( dfs ( i , j , 0 ) for i in range ( m ) for j in range ( n ))

```