单词搜索

[JesseZhao1990]

// 表示某一个点的上右下左的偏移量
var d = [[-1,0],[0,1],[1,0],[0,-1]];
// 标记是否已经被占用
var visited = [];

// 判断是否越界
function inArea(board,x,y){
    return x>=0 && y>=0 && x<board[0].length && y<board.length;
}

function searchWord(board,wordArray,index,x,y){
    if(wordArray.length === index+1){
        return board[y][x] === wordArray[index];
    }
    if(board[y][x] === wordArray[index]){
        visited[y][x] = true;
        for(var i=0;i<4;i++){
            var newY = y + d[i][0];
            var newX = x + d[i][1];
            if(inArea(board,newX,newY) && !visited[newY][newX] && searchWord(board,wordArray,index+1,newX,newY)){
                return true;
            }
        }
        visited[y][x] = false;
    }
    return false;
}

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    visited = [];
    for(var m=0;m<board.length;m++){
        visited.push(new Array(board[0].length).fill(false))
    }
    
    for(var i=0;i<board.length;i++){
        for(var j=0;j<board[i].length;j++){
            if(searchWord(board,word.split(''),0,j,i)){
                return true
            }
        }
    }
    return false;
    
};

解题思路

遍历二维数组，以每个点为起点开始往四周搜索。搜索的过程是一个递归和回溯的过程。

leetcode原题地址：https://leetcode-cn.com/problems/word-search/description/