题解 | #单词搜索#

java版来了

    public boolean exist (String[] board, String word){
        int rowSize = board.length;
        int colSize = board[0].length();
        // 用一个mask数组表示是否被访问过
        boolean[][] mask = new boolean[rowSize][colSize];
        // 遍历不同的起点
        for(int i = 0; i < rowSize; i++){
            for(int j = 0; j < colSize; j++){
                // 只要有一个起点的递归满足了条件就结束，全部起点都找不到路径就返回false
                if (ifExits(board, word, mask, i, j, 0))
                    return true;
            }
        }
        return false;
    }
    private boolean ifExits(String []board, String word, boolean[][] mask, int i, int j, int index){
        // 先判断边界条件
        if(i < 0 || j < 0 || i >= board.length || j >= board[0].length() || mask[i][j])
            return false;
        // 判断当前字符是否是相等的
        if(board[i].charAt(j) == word.charAt(index)){
            // 如果相等并且已经到模式串的边界了，直接返回true
            if(index == word.length() - 1){
                return true;
            }
            // 否则进行一个标记
            mask[i][j] = true;
            // 继续去探索其他的几个方向，不用处理边界，边界在下一次递归开始处理了
            if (ifExits(board, word, mask, i+1, j, index+1) ||
                    ifExits(board, word, mask, i, j+1, index+1) ||
                    ifExits(board, word, mask, i-1, j, index+1) ||
                    ifExits(board, word, mask, i, j-1, index+1)){
                return true;
            }
            // 四个方向都没成功，回退一格，取消此次路径的标记
            mask[i][j] = false;
            // 到这一步说明没找到，返回false
            return false;
        }
        return false;
    }