leetcode-word-search

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/word-search/

　　在一个字母的矩阵中搜索一个单词是否存在

题目分析

　　典型的DFS题目，但要注意不要使用辅助标记数组的方式，很容易超时，每次访问过的点用一个非字母的字符标记一下就可以了

代码

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
35
36
37
38
39
40
41
42
43
public class Solution {
    private int row;
    private int col;
    private int len;
    
    private boolean check(char[][] board, int si, int sj) {
        return (si >=0 && si < row && sj >=0 && sj < col);
    }
    
    private boolean search(char[][] board, int si, int sj, int idx, String word) {
        if (idx > len - 1) {
            return true;
        }
        if (!check(board, si, sj) || word.charAt(idx) != board[si][sj] || board[si][sj] == '.') {
            return false;
        }
        char pre = board[si][sj];
        board[si][sj] = '.'; // 用一个非字母的字符标记
        if(search(board, si - 1, sj, idx + 1, word) || search(board, si + 1, sj, idx + 1, word) || search(board, si, sj - 1, idx + 1, word) || search(board, si, sj + 1, idx + 1, word)) { // 四个方向搜索
            return true;
        }
        board[si][sj] = pre;
        return false;
    }
    
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || board[0].length == 0 || word == null || word.length() == 0) {
            return false;
        }
        row = board.length;
        col = board[0].length;
        len = word.length();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (search(board, i, j, 0, word)) {
                    return true;
                }
            }
        }
        return false;
    }
}