【LeetCode】No.79. Word Search -- Java Version

题目链接：https://leetcode.com/problems/word-search/

1. 题目介绍（Word Search）

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

【Translate】： 给定一个m × n的字符网格board和一个字符串word，如果单词在网格中存在，则返回true。

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.

【Translate】： 这个单词可以由顺序相邻的单元格的字母构成，其中相邻的单元格水平或垂直相邻。同一个字母单元格不能使用多次。

【测试用例】：

【条件约束】：

【跟踪】：

【Translate】： 你能否使用剪枝搜索来使你的解决方案在一个更大的board中运行的更快？

2. 题解

2.1 递归 – O(3 * word.length * m * n)

原题解来自于 JacksonOan 的 Java, Simple with Explanation!

该题解的核心思路就是先找到符合条件的第一个字符，然后以此向上下左右去进行回溯，通过设置边界条件来判断对错。该题还可以扩展成，判断是否有多个符合条件的结果，如果有，有几个?

此外这里的代码与原题解代码略有不同的是去掉了b[r][c] == '0' ，这是因为在正确的回溯过程中，b[r][c]还没有被恢复，仍然处被改变的状态，所有在递归的过程中它就根本不可能出现==word.chatAt(start)的那个值。

class Solution {
    private static int m,n;
    public boolean exist(char[][] board, String word) {
        m = board.length;
        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) && search(board,word,0,i,j)) return true;
            }
        }
        return false;
    }
    
    public boolean search(char[][] b, String w, int index, int i, int j){
        if (i < 0 || i >= m || j < 0 || j >= n || b[i][j] != w.charAt(index)) return false;
        
        if (index == w.length()-1) return true;
        
        char tmp = b[i][j];
        b[i][j] = '0';
        
        if (search(b,w,index+1,i+1,j) ||
           search(b,w,index+1,i-1,j) ||
           search(b,w,index+1,i,j+1) ||
           search(b,w,index+1,i,j-1)) return true;
        
        b[i][j] = tmp;
        return false;
    }
}
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

3. 参考资料

[1] Prune-and-Search | A Complexity Analysis Overview | GeeksforGeeks