my canteen
登录       注册

您现在的位置是:网站首页 > 学无止境

LeetCode(7)-单词搜索

王伟2020年9月13日61人围观
简介LeetCode(7)-单词搜索

LeetCode(7)-单词搜索

DFS与回溯算法

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

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


示例:

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

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

借用笨猪爆破组的两张图应该更好理解

题解思路

1.匹配当前字符word[i]与board[i][j]是否相等 否则直接返回false 进行下一个的比较

2.匹配到当前字符后,根据上图的四个方向进行递归,并且判断是否越界

3.匹配单词末尾后直接return true

4.特别注意:上图访问过的节点进行标记,以免重复访问,并且当此次单词链走不通时,将标记节点还原

var exist = function (board, word) {
    if (board.length === 0) return false;
    if (word.length === 0) return true;
    const row = board.length;
    const col = board[0].length;
    for(let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if(find(i,j,0)) return true;
        }
    }
    return false;
    function find(i, j, cur) {
        if(i >= row || i < 0 || j >=col || j < 0) return false;
        const cur = board[i][j];
        if(cur !== word[cur]) return false;
        if(cur === word.length - 1) return true;
        board[i][j] = null;
        const res = find(i+1,j,cur+1) ||
                    find(i-1,j,cur+1) ||
                    find(i,j+1,cur+1) ||
                    find(i,j-1,cur+1);
        board[i][j] = cur; // 还原标记节点
        return res;
    }
};

路漫漫其修远兮,吾将上下而求索!


文章评论

来说句话吧.... 共有评论数:0条


微信二维码 博主微信 qq二维码 博主QQ
177****8743
7*24小时电话