We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
There was an error while loading. Please reload this page.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
给定一个二维网格和一个单词,找出该单词是否存在于网格中。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] 给定 word = "ABCCED", 返回 true 给定 word = "SEE", 返回 true 给定 word = "ABCB", 返回 false
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/word-search 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这是一个比较经典的可以用递归回溯法来解决的二维数组问题,这里用到几个技巧:
[[-1, 0], [1, 0], [0, -1], [0, 1]]
左、右、上、下
visited
inArea
有了这些辅助方法后,接下来就需要创建一个递归函数 search,它接受的参数为:
search
startX
startY
wordIndex
在这个递归函数中,如果当前的 x、y 在二维数组中对应的字符和 wordIndex 所对应的字符匹配一致的话,并且 wordIndex 还没有到字符串的最后一位的话,就继续递归的向 上、下、左、右四个方向进一步递归匹配字符串的下一个下标 wordIndex + 1即可。
x
y
上、下、左、右
wordIndex + 1
当 wordIndex 成功的来到字符串的最后一位下标后,即可根据最后一位字符是否匹配当前的 x、y 来决定本次整个递归的返回值。
主函数中,只需要遍历整个二维数组,不断的以当前的坐标和 wordIndex = 0 开始从第一个字符遍历,只要 search 函数返回 true,就说明匹配成功,整体返回 true 结果即可。
wordIndex = 0
/** * @param {character[][]} board * @param {string} word * @return {boolean} */ let directions = [ [-1, 0], [1, 0], [0, -1], [0, 1], ] // 左 右 上 下 let exist = function (board, word) { let maxY = board.length if (!maxY) return false let maxX = board[0].length // 二维数组记录已访问过的元素 let visited = new Array(maxY) for (let y = 0; y < visited.length; y++) { visited[y] = new Array(maxX) } let inArea = (x, y) => { return x >= 0 && x < maxX && y >= 0 && y < maxY } let search = (startX, startY, wordIndex) => { // 当前起始字符不匹配 直接失败 let curCell = board[startY][startX] let curChar = word[wordIndex] if (curCell !== curChar) { return false } // 如果递归到最后一位字符 就直接返回最后一位字符是否匹配成功 if (wordIndex === word.length - 1) { return curChar === curChar } // 进一步递归 先记录为已访问元素 防止递归的时候重复访问 visited[startY][startX] = true for (let direction of directions) { let [x, y] = direction let nextX = startX + x let nextY = startY + y // 需要保证未越界且未被访问过 if (inArea(nextX, nextY) && !visited[nextY][nextX]) { if (search(nextX, nextY, wordIndex + 1)) { return true } } } // 重置已访问标记位 visited[startY][startX] = false } for (let y = 0; y < maxY; y++) { for (let x = 0; x < maxX; x++) { if (search(x, y, 0)) { return true } } } return false }
The text was updated successfully, but these errors were encountered:
No branches or pull requests
Uh oh!
There was an error while loading. Please reload this page.
给定一个二维网格和一个单词,找出该单词是否存在于网格中。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/word-search
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
这是一个比较经典的可以用递归回溯法来解决的二维数组问题,这里用到几个技巧:
[[-1, 0], [1, 0], [0, -1], [0, 1]]
这样的数组来标记访问左、右、上、下
位置需要偏移的坐标量。visited
来标记已访问过的元素,防止在递归的过程中重复访问,陷入死循环。inArea
函数来判断接下来要访问的元素是否超出整个二维数组的边界。递归函数
有了这些辅助方法后,接下来就需要创建一个递归函数
search
,它接受的参数为:startX
:本次匹配字符的起始 X 坐标。startY
:本次匹配字符的起始 Y 坐标。wordIndex
:本次需要匹配的字符串下标,在前一个下标已经成功匹配后才会进一步累加。在这个递归函数中,如果当前的
x
、y
在二维数组中对应的字符和wordIndex
所对应的字符匹配一致的话,并且wordIndex
还没有到字符串的最后一位的话,就继续递归的向上、下、左、右
四个方向进一步递归匹配字符串的下一个下标wordIndex + 1
即可。当
wordIndex
成功的来到字符串的最后一位下标后,即可根据最后一位字符是否匹配当前的x
、y
来决定本次整个递归的返回值。主函数
主函数中,只需要遍历整个二维数组,不断的以当前的坐标和
wordIndex = 0
开始从第一个字符遍历,只要search
函数返回 true,就说明匹配成功,整体返回 true 结果即可。The text was updated successfully, but these errors were encountered: