LeetCode(BackTracking)Word Search

2018-06-25

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.

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.

思路：回溯法来解决，定义一个二维的flag数组来表示每一个点是否已经被找过，还没找过标志为false，这个点已经找过标志位true。然后利用回溯法的思想：首先在二维的board中找到和给定的字符串第一个字符相等的位置，然后从这个位置出发，再从各个方向查找（此时就可以用到递归来查找），在查找过程中越过边界或者遇到已经找过的点，就标记为false，当前路径下不再查找该点，最后直到遍历到给定字符串的最后一个字符，这时候，我们可以确定，之前的所有字符都在board中找到，存在连续的表示，所以当最后一个字符找完以后如果全部找到就返回true，否则返回false.。

代码如下：

class Solution {
   public boolean exist(char[][] board, String word) {
        int row = board.length;
        if (board == null || row == 0 || word == null || word.length() == 0) {
            return false;
        }
        int col = board[0].length;
        boolean [][] flag = new boolean [row][col];
        for (int i = 0; i < row ; i++) {
            for (int j=0; j < col; j++) {
                if (board[i][j] == word.charAt(0)) {
                   if(backtrack(board, word, i ,j, 0, flag)){
                       return true;
                   }
                }
            }
        }
        return false;
    }
    public boolean backtrack (char [][] board, String word, int i, int j, int k, boolean [][] flag){
        int row = board.length;
        int col = board[0].length;
        if (k == word.length()) {
            return true;
        }
        if (i < 0 || i >= row || j < 0 || j >= col || word.charAt(k) != board[i][j] || flag[i][j] == true){
            return false;
        }
        flag[i][j] = true;
        
        if (backtrack(board, word, i-1, j, k+1, flag) || 
            backtrack(board, word, i+1, j, k+1, flag) ||
            backtrack(board, word, i, j-1, k+1, flag) ||
            backtrack(board, word, i, j+1, k+1, flag)) {
             return true;
        }
        flag[i][j] = false;
        return false;
    }
}