本文主要是介绍LeetCode 79.单词搜索,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
原题链接:. - 力扣(LeetCode)
给定一个 m x n
二维字符网格 board
和一个字符串单词 word
。如果 word
存在于网格中,返回 true
;否则,返回 false
。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1:
输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出:true
示例 2:
输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" 输出:true
示例 3:
输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" 输出:false
提示:
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board
和word
仅由大小写英文字母组成
思路:
本题可采用回溯的方法解决。对于 word 字符串,每匹配到一个字符 word.charAt(p) 后(假设在 board[ i ][ j ] 处匹配到),就递归匹配下一个字符 word.charAt(p+1)(在 board[ i ][ j + 1]、board[ i ][ j - 1]、board[ i +1 ][ j ]、board[ i +1 ][ j ] 处去尝试匹配),如此类推。同时注意到对已经匹配的字符需要加一个标识,避免其被再次匹配到(可以给已经匹配的字符加一个 - 号,让其不能再和word 中的字符匹配到)。
终止条件:假如 p == word.length(),则说明匹配成功。将 found 设置为 true,返回。假如 found 为 true,则说明之前已经匹配成功,返回,退出递归。假如 传入的 i,j 不在 board 范围内,返回。假如 board[ i ][ j ] 和 word.charAt(p) 不匹配,那么也退出当前这层递归,返回。
若匹配成功,则需要给 board[ i ][ j ] 加上一个已匹配的标识,然后去 board[ i ][ j ] 的上下左右四个方位去继续匹配下一个字符。最后还需要取消标识,进行回溯。
代码:
class Solution {boolean found = false;public boolean exist(char[][] board, String word) {int n = board.length,m=board[0].length;for(int i=0;i<n;i++){for(int j=0;j<m;j++){dfs(board,i,j,word,0);if(found){return true;}}}return false;}public void dfs(char[][] board,int i,int j,String word,int p){//word已经被匹配完毕,匹配成功if(p==word.length()){found = true;return;}if(found){return;}int n = board.length, m = board[0].length;if(i<0||j<0||i>=n||j>=m){return;}//若(i,j)处的字符不匹配word[p]if(board[i][j]!=word.charAt(p)){return;}//board(i,j)处的字符匹配上了word[p]//做个标记,避免匹配上的字符再被匹配board[i][j]= (char)(-board[i][j]);dfs(board,i,j-1,word,p+1);dfs(board,i,j+1,word,p+1);dfs(board,i-1,j,word,p+1);dfs(board,i+1,j,word,p+1);board[i][j]= (char)(-board[i][j]);}
}
这篇关于LeetCode 79.单词搜索的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!