LeetCode 79. Word Search

[Woodyiiiiiii]

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.

Constraints:

• board and word consists only of lowercase and uppercase English letters.
• 1 <= board.length <= 200
• 1 <= board[i].length <= 200
• 1 <= word.length <= 10^3

---

这道题跟200. Number of Islands很类似。用DFS+回溯的方法来做，遍历二维数组，然后对每个元素进行深度遍历(用boolean类型的二维数组v来作为访问标志)。

DFS+回溯法要注意的是每次调用递归参数时传入的参数，会不会有什么影响，还有回溯后的某些变量有没有改变。比如，这道题中，每次回溯回来后的**v[i][j]**要重新设为false，以便其他元素的深度遍历，还有字符串作为参数要传递新值(new String)，不然回溯回来后要截取一段字符串。

class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        boolean[][] v = new boolean[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (check(board, v, i, j, word, new String("")))
                    return true;
            }
        }
        return false;
    }
    boolean check(char[][] board, boolean[][] v, int i, int j,
                    String word, String s) {
        if (v[i][j]) return false;
        if (s.length() >= 1 &&
                s.charAt(s.length() - 1) != word.charAt(s.length() - 1))
            return false;
        v[i][j] = true;
        s += board[i][j];
        if (s.equals(word)) return true;
        boolean res = false;
        if (i - 1 >= 0) {
            res = check(board, v, i - 1, j, word, new String(s));
            if (res) return true;
        }
        if (j - 1 >= 0) {
            res = check(board, v, i, j - 1, word, new String(s));
            if (res) return true;
        }
        if (i + 1 < board.length) {
            res = check(board, v, i + 1, j, word, new String(s));
            if (res) return true;
        }
        if (j + 1 < board[0].length) {
            res = check(board, v, i, j + 1, word, new String(s));
            if (res) return true;
        }
        v[i][j] = false;
        return false;
    }
}

上述解法是我第一遍花了很多时间磕磕绊绊地做出来的，因为一开始没搞懂回溯回来的v要设为false，并且后面四串相同模板的代码片段有些冗余了。而且，如果不加每步判断字符是否对应目标字符串word的字符(剪枝优化)，会出现超时“Time Exceed”。

所以我优化了下代码，我们不用一个生成字符串来跟目标字符串word来作比较，只用一个下标值对应word的下标，和每次遍历的board[i][j]来比较，这样的明显优化了运行时间。

class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        boolean[][] v = new boolean[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (check(board, v, i, j, word, 0))
                    return true;
            }
        }
        return false;
    }
    boolean check(char[][] board, boolean[][] v, int i, int j,
                    String word, int idx) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length
            || v[i][j] || board[i][j] != word.charAt(idx)) 
            return false;
        if (idx + 1 == word.length()) return true;
        v[i][j] = true;
        boolean res = check(board, v, i - 1, j, word, idx + 1)
                    || check(board, v, i, j - 1, word, idx + 1)
                    || check(board, v, i + 1, j, word, idx + 1)
                    || check(board, v, i, j + 1, word, idx + 1);
        v[i][j] = false;
        return res;
    }
}

---

参考资料：

• https://leetcode.com/problems/word-search/
• [LeetCode] 79. Word Search grandyang/leetcode#79