79.单词搜索

题目描述

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例：

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

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

思路

1.本题可以使用回溯算法求解。
2.我们可以设置二维数组的上下左右四个偏移量，并在挪到特定偏移量后通过一个记录器记录当前状态，一直递归下去，若不合适便回溯到外层，并将该偏移量记录抹去即可。
3.最后在按照偏移量移动时，判断该位置是否越界即可。

Java代码实现

    public boolean exist(char[][] board, String word) {
        if(board.length == 0){
            return false;
        }
        boolean[][] memory = new boolean[board.length][board[0].length];
        int[][] direction = {{0,1},{1,0},{-1,0},{0,-1}};
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(exist(board,word,i,j,0,memory,direction)){
                    return true;
                }
            }
        }
        return false;
    }

    /**
     *
     * @param board  输入的二维数组
     * @param word   输入的字符串
     * @param row    当前递归到的行
     * @param col    当前递归到的列
     * @param startIndex    输入字符串的起始坐标
     * @param memory        递归记录
     * @Param direction     方向向量
     * @return
     */
    private boolean exist(char[][] board, String word,int row, int col,int startIndex,boolean[][] memory,int[][] direction){
        //递归结束条件，比较最后一个字符
        if(startIndex == word.length()-1){
            return board[row][col] == word.charAt(startIndex);
        }

        //判断当前位置是否进入递归
        if(board[row][col] == word.charAt(startIndex)){
            for (int i = 0; i < 4; i++) {
                //记录该位置不可以再被走
                memory[row][col] = true;

                //偏移量
                int newRow = row + direction[i][0];
                int newCol = col + direction[i][1];

                //判断当前位置是否可以走
                if(!isOut(board,newRow,newCol) && !memory[newRow][newCol]){
                    if(exist(board,word,newRow,newCol,startIndex+1,memory,direction)){
                        return true;
                    }
                }
            }
            //抹掉该位置的记录
            memory[row][col]= false;
        }
        return false;
    }

    //判断是否越界
    private boolean isOut(char[][] board,int row,int col){
        if(row<0 || col <0 || row >= board.length || col >= board[0].length)
            return true;
        return false;
    }

Golang代码实现

func exist(board [][]byte, word string) bool {
    for i:=0; i<len(board);i++{
        for j:=0;j<len(board[0]);j++{
            if existDFS(i,j,board,0,word){
                return true
            }
        }
    }
    return false
}

func existDFS(row int,col int,board [][]byte,pos int,word string) bool{
    //匹配成功
    if pos == len(word){
        return true
    }

    //超过边界
    if row < 0 || col < 0 || row >= len(board) || col >= len(board[0]){
        return false
    }

    //当前不匹配 直接返回false
    if board[row][col] != word[pos]{
        return false
    }

    //这样便不会往回走
    board[row][col] += 128

    if existDFS(row-1,col,board,pos+1,word) || existDFS(row+1,col,board,pos+1,word) ||
        existDFS(row,col-1,board,pos+1,word) || existDFS(row,col+1,board,pos+1,word){
        return true
    }

    board[row][col] -= 128

    return false
}