# 79. Word Search (backtracking)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MB3dZyEyZToFZwZmOTa%2F-MB49WI-Hc88WWZy5fUQ%2Fimage.png?alt=media\&token=43635ea8-5320-4e79-9f14-5cf095ff14ed)

Given a 2D board and a word, find if the word exists in the grid.

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

**avoid using a boolean array to store used, just set  " board\[i]\[j] = '   ' "**

```
visited = new boolean[board.length][board[0].length];
```

```java
class Solution {
    public boolean exist(char[][] board, String word) {
        for (int i = 0 ; i < board.length; i++) {
            for (int j = 0; j < board[i].length;j++) {
                if (board[i][j] == word.charAt(0) && dfs(board, i, j, 0, word)) {
                    return true; // if find first char, and dfs search ok
                }
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board,int i, int j, int count, String word) {
        if (count == word.length()) { // length equals to ori word, good!
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[i].length 
            || board[i][j] != word.charAt(count)) {
            return false; // outboud
        }
        
        char temp = board[i][j]; // backtracking
        board[i][j] = ' '; // set to empty to represent used
        // use or, so can't use dirs[]
        boolean result = 
            dfs(board, i + 1, j, count+1, word) ||
            dfs(board, i - 1, j, count+1, word) ||
            dfs(board, i, j + 1, count+1, word) ||
            dfs(board, i, j - 1, count+1, word);
        board[i][j] = temp; // add back
        return result;
    }
}
```

## with pruning

```java
class Solution {
    private static final int[][] DIRS = {{0,1},{0,-1},{1,0},{-1,0}};
    public boolean exist(char[][] grid, String word) {
        
        if (!pruning(grid, word)) {
            return false;
        }
        
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == word.charAt(0) && dfs(grid, word, 0, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }
    private boolean pruning(char[][] grid, String word) {
        int m = grid.length;
        int n = grid[0].length;
        
        // pruning: case 1: not enough characters in board
        if (word.length() > m * n) {
            return false;
        }
        
        // pruning: case 2: board does not contain characters or enough characters that word contains
        Map<Character, Integer> count = new HashMap<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int temp = count.getOrDefault(grid[i][j], 0);
                count.put(grid[i][j], temp + 1);
            }
        }
        
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!count.containsKey(c)) {
                return false; // cant find word's char in hashmap
            } else { // remove count one by one, because word maybe duplicate
                int temp = count.get(c);
                if (temp == 1) {
                    count.remove(c);
                } else {
                    count.put(c, temp - 1);
                }
            }
        }
        return true;
    }
    
    private boolean dfs(char[][] grid, String word, int start, int i, int j) {
        if (start == word.length()) {
            return true;
        }
        if (!isValid(grid, i, j) || word.charAt(start) != grid[i][j]) {
            return false;
        }
        
        char temp = grid[i][j];
        grid[i][j] = ' ';
        
        boolean result = false;
        for (int[] dir : DIRS) {
            result = dfs(grid, word, start + 1, i + dir[0], j + dir[1]);
            if (result) { // find 就 break
                break;
            }
        } 
        
        grid[i][j] = temp;
        return result;
    }
    private boolean isValid(char[][] grid, int i, int j) {
        return i >= 0 && i < grid.length && j >= 0 & j < grid[0].length;
    }
}

/*
dfs search

how to ?

put first word in dfs search, then 4 direction

dfs() {
 if (start == word.length()) {
    return true;
 }
 
 if (4 direction) {
    get result
    if (not ok return false)
 }
 return result
}
*/
```

## new version, this is more intutive&#x20;

## use visited

```java
class Solution {
    private static final int[][] DIRS = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    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++) {
                if (board[i][j] == word.charAt(0) && dfs(board, word, 0, i, j, new boolean[m][n])) {
                    return true;
                }
            }
        }
        return false;
    }
    private boolean dfs(char[][] board, String word, int start, int i, int j, boolean[][] visited) {
        if (start == word.length()) {
            return true;
        }
        if (!inArea(board, i, j) || visited[i][j] || word.charAt(start) != board[i][j]) {
            return false;
        }

        visited[i][j] = true; 
        for (int[] dir : DIRS) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (dfs(board, word, start+1, x, y, visited)) {
                return true;
            }
        }
        visited[i][j] = false; 
        return false;
    }
    private boolean inArea(char[][] board, int x, int y) {
        return x >= 0 && x < board.length && y >=0 && y < board[0].length;
    }
}
/*
needs match word[0] to start

for (board)

if (ij == word[0]) {
    dfs(start, i, j, )
}
retur

start == word.length
*/
```

### not use visited

以後還是寫在外面好了

```java
class Solution {
    private static final int[][] DIRS = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    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++) {
                if (board[i][j] == word.charAt(0) && dfs(board, word, 0, i, j)) {
                    return true; // 為什麼都找到第一個字了, 還要傳 index 0 進去？
                } // 因為 mark 是在 dfs 裡面做的, backtracking 也是
            }
        }
        return false;
    }
    private boolean dfs(char[][] board, String word, int start, int i, int j) {
        if (start == word.length()) {
            return true;
        }
        if (!inArea(board, i, j) || word.charAt(start) != board[i][j]) {
            return false;
        }
        char temp = board[i][j];
        board[i][j] = ' '; 
        for (int[] dir : DIRS) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (dfs(board, word, start+1, x, y)) {
                return true;
            }
        }
        board[i][j] = temp; 
        return false;
    }
    private boolean inArea(char[][] board, int x, int y) {
        return x >= 0 && x < board.length && y >=0 && y < board[0].length;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/dfs/tips/79.-word-search.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.