 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
79. Word Search
Medium

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.

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

##解题思路：主要是用回溯算法来做，分别尝试 i+1, i - 1, j+1, j -1 四个方向。因为每个元素都只访问一次，所以需要用board[i][j]=’#’ 来标注，把值用中间变量c 保存起来，回溯的时候，board[i][j] = c.
另外第二种常规思路，就是用visited[][] 来记录访问情况，但是这种办法需要额外空间。第三种处理方式，我没看吃透， board[i][j] ^= 256 来做标记，处理结束以后，再用board[i][j] ^= 256 回溯。

简单的代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
    public boolean exist(char[][] board, String word) {
        // Ref: https://leetcode.com/problems/word-search/discuss/27834/Simple-solution
       if (board == null || board.length == 0 &&  board[0].length < word.length()) return false;
        char[] target = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (search(board, i, j, 0, target)) return true;
            }
        }
        return false;
    }
                    
    
    
    private boolean search(char[][] board, int i, int j, int pos, char[] target) {
        if (pos >= target.length ) return true;
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return false;
        
        if (board[i][j] == target[pos]) {
            char c = board[i][j];
            board[i][j] = '#';
         
           boolean  res = search(board, i + 1, j, pos + 1, target) ||
                search(board, i , j + 1, pos + 1, target)||
                search(board, i - 1, j, pos + 1, target) ||
                search(board, i, j - 1, pos + 1, target);
            board[i][j] = c;
            return res;
        } 
        return false;
    }
}

运行结果

1
2
3
4
5
6
7
Success

[Details](https://leetcode.com/submissions/detail/252920160/)

Runtime: 3 ms, faster than 99.90% of Java online submissions for Word Search.

Memory Usage: 38.7 MB, less than 95.92% of Java online submissions for Word Search.

文章目录

简单的代码

运行结果