力扣是什么意思，力扣548

最初的问题给你一个二维网格和一个单词，你想检查该单词是否存在于网格中。

单词必须由按字母顺序相邻的单元格中的字母组成。 “相邻”单元是水平或垂直相邻的单元。同一单元格中不能重复字符。

示例：

板=[ [\’A\’,\’B\’,\’C\’,\’E\’], [\’S\’,\’F\’,\’C\’,\’S\’], [\’A\’,\’D\’,\’E \’,\’E\’]] 如果word=\’ABCCED\’，则返回true。如果word=\’SEE\’，则返回true。原问题网址：https://leetcode-cn.com/issues/word。 -搜索/

解决问题

回顾这个问题，我最初是这样想的：

从每个网格开始搜索。检查当前字符和与其连接的下一个字符（上、下、左、右）是否满足条件后，搜索条件继续。除非当前不一致，否则会立即返回false 并立即失败。使用二维布尔数组记录每个单元格的使用情况。请注意，如果无法从当前单元格开始，则需要返回。现在让我们看一下代码。

class Solution { //总行数int row; //总列数intcol //要搜索的字符数组char[] wordArray; ][] board, String word) { this.board=board this.col=board; [0 ].length; //标记每个单元格。 used 2D 数组boolean[][]used=new boolean[row][col]; //从每个单元格开始搜索for (int i=0; i row; i++) { for (int j=0; j column; j++ ) { if (dfs(i, j, 0,used)) { return true } } } return false } public boolean dfs(int x, int y, int index, boolean[][]used) { //当前是否位置满足条件if (board[x][y] !=wordArray[index]) { return false } //全部找到if (index==wordArray.length – 1) { return true ;使用的网格used[x][y]=true; //检查顶部/底部/左/右是否匹配//先前的网格是否存在请检查是否。未使用if (x 0 !used[x – 1][y]) { if (dfs(x – 1, y, Index + 1,used)) { return true } } //下一个单元格是否存在，无论是否并且是未使用if (x row – 1 !used[x + 1][y]) { if (dfs(x + 1, y, Index + 1,used)) { return true } } //左侧或不存在单元格但存在notused if (y 0 !used[x][y – 1]) { if (dfs(x, y – 1,index + 1,used) ) { return true } //右边的单元格存在但是未使用if (ycol – 1 !used[x][y + 1]) { if (dfs(x, y + 1, Index + 1,used)) { return true } //现在所有的上/下； /左/右情况都没有了，返回退出，设置当前网格不使用used[x][y]=false }} 提交OK，执行时间：19 ms，内存消耗：38.3 MB。看起来时间上还有优化的空间，但是怎么办呢？

看起来像是一种浪费的优化，但我研究了其他人更好的解决方案，发现想法是相同的，但如果决策很快失败，可能会更简洁。似乎没有什么本质区别。我稍微优化了写作风格。

class Solution { //总行数int row; //总列数intcol //要搜索的字符数组char[] wordArray; ][] board, String word) { this.board=board this.col=board; [0 ].length; //标记每个单元格。 used 2D 数组boolean[][]used=new boolean[row][col]; //从每个单元格开始搜索for (int i=0; i row; i++) { for (int j=0; j column; j++ ) { if (dfs(i, j, 0,used)) { return true } } } return false } public boolean dfs(int x, int y, int index, boolean[][]used) { //返回失败if当前位置不存在或被使用if (x 0 || x=row || y 0 || y=col ||used[x][y]) { return false } //当前位置是否满足条件if (board[x][y] !=wordArray[index]) { return false; } //全部找到if (index==wordArray.length – 1 ) { return true; //设置当前使用的网格[y]=true //检查上、下、左、右条件是否符合以下条件boolean flag=dfs(x – 1 , y,index; + 1,used) || dfs(x + 1 , y ,index + 1,used) || dfs(x, y + 1,index + 1) ,used); //上、下、左、右转到。现在您已完成，将当前网格设置为未使用。 used[x][y]=false }}发送OK，执行时间。5ms，内存消耗：38.4MB。尽管花费的时间要少得多，但您应该根据以下因素做出决定：

关于判断一个位置是否存在，以前的方法是判断下一个位置是否存在，但是分为四个if测试，现在是通过一个if测试来判断。如果要向上、向下、向左、向右搜索，逻辑运算符|| 支持短路，因此会得到与之前分成四个if 类似的效果，但看起来更简洁。好吧，实际上，我不明白为什么这样写可以节省时间。如果您知道，请在下方留言。

总结一下，以上就是我对这个问题的回答过程。不知道大家是否明白。这个问题主要是关于回溯的。没有其他问题。

如果您有兴趣，请访问我的博客或关注我的公众号和今日头条号。你可能会得到意想不到的惊喜。

https://death00.github.io/

公众号：健康之旅路径