Word Search 08/07

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.Have you met this question in a real interview? Yes

Example

Given board =

[
  "ABCE",
  "SFCS",
  "ADEE"
]

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

基本想法比较类似： 遍历board找到第一个和word打头字母一样的， 开始计算它的上，下，左，右坐标。看是否能找到word的第二个字母。依次类推... 用visited二维数组记录board中每一个字母被访问过的情况，如果一个字母被访问过，下一个字母再次访问到该字母的时候，要跳过。 判断是否当下字母是valid的字母的条件： 1. 不能出界； 2.之前被访问过； 3.和当下word对应的字母不一样 用pos加在dfs函数中作为参数，每次递归一次+1， 用来记录当前要找的是word中的第几位字母。

public class Solution {
    /**
     * @param board: A list of lists of character
     * @param word: A string
     * @return: A boolean
     */
     
    private static int[] xPositon = {0,1,0,-1};
    private static int[] yPositon = {1,0,-1,0};
    
    public boolean exist(char[][] board, String word) {
        // write your code here
        
        if(board == null || board.length == 0 || board[0].length == 0 ){
            return false;
        }
        
        boolean[][] isVisited = new boolean[board.length][board[0].length];
        
        for (int i = 0; i < board.length ;++i ){
            for(int j = 0; j < board[0].length;++j){
                if(board[i][j] != word.charAt(0)){
                    continue;
                }
                
                isVisited[i][j] =true;
                if(dfs(i,j,isVisited,word,1,board)){
                    return true;
                }
            }
        } 
        
        return false;
    }
    
    public boolean dfs(int i, int j, boolean[][] isVisited,String word,int pos,char[][] board){
        
        if(pos == word.length()){
            return true;
        }
        
        for(int k = 0; k < 4; ++k){
            int x = i + xPositon[k];
            int y = j + yPositon[k];
            
            if(!isGood(isVisited,word,x,y,pos,board)){
               continue;
            }
            
            isVisited[x][y] = true;
            if(dfs(x,y,isVisited,word,pos+1,board)){
                return true;
            }
            
            isVisited[x][y] = false;
        }
        
        return false;
        
    }
    
    public boolean isGood(boolean[][] isVisited,String word,int x,int y,int pos,char[][]board){
        if(x <0 || x >= board.length || y < 0 || y >= board[0].length || isVisited[x][y]|| board[x][y] != word.charAt(pos)){
            return false;
        }
        
        return true;
    }
}