> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/dfs/tips/79.-word-search.md).

# 79. Word Search (backtracking)

![](/files/-MB49WI-Hc88WWZy5fUQ)

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;
    }
}
```