leetcode: Word Search

问题描述：

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.

For example,
Given board =

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

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

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

 

问题分析

　　这个问题有一种典型的思路，就是深度优先遍历的办法。因为要在矩阵里查找到一个符合字符串长度的串。我们在实现的时候会考虑到遍历矩阵里的每个位置，看它是否和给定的串匹配。

　　在判断匹配的过程中，我们会用一个对应的boolean[][] matrix矩阵来保存递归遍历过程中访问过的元素。所以在碰到一个当前元素和字符串当前位置元素相等的情况下，我们就要将对应位置的matrix[i][j] 为设置为true。然后再去看它周围的４个点。这几个点中间符合条件的元素必须满足它们即在这个矩阵里，而且又没有被访问过。而这个递归调用的函数如果能够返回，则说明当前访问到的元素位置已经到达了给定串的长度。

　　代码里还有一个细节就是，每次遍历完一个点之后，如果它所访问过的路径并不匹配，则需要将访问过的当前元素位置重置回来。这里是一个非常容易出错的地方。

详细的代码实现如下：

 

public class Solution {
    public boolean exist(char[][] board, String word) {
        if(board == null || word == null || word.isEmpty()) return false;
        int m = board.length, n = board[0].length;
        boolean[][] accessed = new boolean[m][n];
        for(int i = 0; i < m; i++) 
            for(int j = 0; j < n; j++) 
                if(dfs(board, word, 0, i, j, accessed)) return true;
        return false;
    }
    
    private boolean inBoard(int i, int j, char[][] board) {
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length)
            return false;
        return true;
    }
    
    private boolean dfs(char[][] board, String word, int cur, int i, int j, boolean[][] matrix) {
        if(cur == word.length()) return true;
        if(inBoard(i, j, board)) {
            if(board[i][j] == word.charAt(cur) && !matrix[i][j]) {
                matrix[i][j] = true;
                if(dfs(board, word, cur + 1, i + 1, j, matrix)) return true;
                else if(dfs(board, word, cur + 1, i - 1, j, matrix)) return true;
                else if(dfs(board, word, cur + 1, i, j + 1, matrix)) return true;
                else if(dfs(board, word, cur + 1, i, j - 1, matrix)) return true;
                matrix[i][j] = false;
                return false;
            }
        }
        return false;
    }
}