Word Search

题意:在二维字符表中查找目标字符串,不能重复访问单元格,主要是找到入口+深度搜索然后标记访问过得单元即可

public class Solution {
    
    public  boolean exist(char[][] board, String word) {
        if (word == null || word.length() == 0 || board == null || board.length == 0) return false;


        boolean isExist = false;


        int xmax = board.length;//获取board的长宽
        int ymax = board[0].length;
        for (int i = 0; i < xmax; ++i) {
            for (int j = 0; j < ymax; ++j) {
                if (word.charAt(0) == board[i][j]) {
                    isExist = isFind(board, i, j, word, 0);
                    if (isExist) return isExist;
                } else {
                    continue;
                }
            }
        }
        return isExist;
    }


    /**
     * 查找函数
     *
     * @param board
     * @param x     (x,y)当前位置
     * @param y
     * @param word
     * @param index
     * @return
     */
    public  boolean isFind(char[][] board, int x, int y, String word, int index) {
        boolean find = false;
        if (index == word.length())return true;
        final char BLANK = '0';
        if(x<0 || y<0 ||x >= board.length || y>=board[x].length
                || board[x][y]== BLANK ||board[x][y] != word.charAt(index))
            return false;
        else {
            board[x][y] = BLANK;
            find = isFind(board, x + 1, y, word, index + 1)
                    ||isFind(board, x - 1, y, word, index + 1)
                    ||isFind(board, x, y + 1, word, index + 1)
                    ||isFind(board, x, y - 1, word, index + 1);
            board[x][y] = word.charAt(index);
            return find;
        }
    }




    


}

Word Search

原文：http://blog.csdn.net/youmengjiuzhuiba/article/details/44588523