算法leetcode｜79. 单词搜索（rust重拳出击）

文章目录

79. 单词搜索：

给定一个

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 仅由大小写英文字母组成

进阶：

• 你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

分析：

• 面对这道算法题目，二当家的再次陷入了沉思。
• 需要尝试所有的可能，遍历是不可少的，使用循环或者递归，递归是首选，因为比较容易实现，深度优先，回溯，递归套娃大法好。
• 需要遍历每一个元素，然后开始从每个位置使用递归套娃大法，分别向上，下，左，右四个方向进行递归，重复操作，直到匹配成功，或者匹配失败就回溯尝试其他，需要注意的是不走重复的位置，所以需要一个结构标记已经走过的位置，使用和原二维字符网格相同大小的结构比较容易，空间上应该还可以优化，但是没有深究，因为空间上并没有浪费，如果做优化，肯定是以牺牲效率为代价，所谓时间换空间，我不要换。

题解：

rust：

implSolution{pubfnexist(board:Vec<Vec<char>>, word:String)->bool{fncheck(board:&Vec<Vec<char>>, word:&Vec<char>, idx:usize, visited:&mutVec<Vec<bool>>, r:usize, c:usize)->bool{if r >= visited.len()|| c >= visited[0].len()|| visited[r][c]|| board[r][c]!= word[idx]{returnfalse;}if idx == word.len()-1{// 完全匹配returntrue;}
            visited[r][c]=true;// 上下左右递归套娃大法ifcheck(board, word, idx +1, visited, r -1, c)||check(board, word, idx +1, visited, r +1, c)||check(board, word, idx +1, visited, r, c -1)||check(board, word, idx +1, visited, r, c +1){returntrue;}
            visited[r][c]=false;returnfalse;}let word = word.chars().collect::<Vec<_>>();letmut visited =vec![vec![false; board[0].len()]; board.len()];for r in0..board.len(){for c in0..board[0].len(){ifcheck(&board,&word,0,&mut visited, r, c){returntrue;}}}returnfalse;}}

go：

funcexist(board [][]byte, word string)bool{
    visited :=make([][]bool,len(board))for i :=range visited {
        visited[i]=make([]bool,len(board[0]))}var check func(idx, r, c int)bool
    check =func(idx, r, c int)bool{if r <0|| r >=len(board)|| c <0|| c >=len(board[0])|| visited[r][c]|| board[r][c]!= word[idx]{returnfalse}if idx ==len(word)-1{// 完全匹配returntrue}
        visited[r][c]=true// 上下左右递归套娃大法ifcheck(idx+1, r-1, c)||check(idx+1, r+1, c)||check(idx+1, r, c-1)||check(idx+1, r, c+1){returntrue}
        visited[r][c]=falsereturnfalse}for r, row :=range board {for c :=range row {ifcheck(0, r, c){returntrue}}}returnfalse}

c++：

classSolution{private:boolcheck(vector<vector<char>>& board, string& word,int idx, vector<vector<bool>>& visited,int r,int c){if(r <0|| r >= visited.size()|| c <0|| c >= visited[0].size()|| visited[r][c]|| board[r][c]!= word[idx]){returnfalse;}if(idx == word.size()-1){// 完全匹配returntrue;}
        visited[r][c]=true;// 上下左右递归套娃大法if(check(board, word, idx +1, visited, r -1, c)||check(board, word, idx +1, visited, r +1, c)||check(board, word, idx +1, visited, r, c -1)||check(board, word, idx +1, visited, r, c +1)){returntrue;}
        visited[r][c]=false;returnfalse;}public:boolexist(vector<vector<char>>& board, string word){
        vector<vector<bool>>visited(board.size(),vector<bool>(board[0].size(),false));for(int r =0; r < board.size();++r){for(int c =0; c < board[0].size();++c){if(check(board, word,0, visited, r, c)){returntrue;}}}returnfalse;}};

python：

classSolution:defexist(self, board: List[List[str]], word:str)->bool:defcheck(idx:int, r:int, c:int)->bool:if r <0or r >=len(board)or c <0or c >=len(board[0])or visited[r][c]or board[r][c]!= word[idx]:returnFalseif idx ==len(word)-1:returnTrue
            visited[r][c]=Trueif check(idx +1, r -1, c)or check(idx +1, r +1, c)or check(idx +1, r, c -1)or check(idx +1, r, c +1):returnTrue
            visited[r][c]=FalsereturnFalse

        visited =[[False]*len(board[0])for _ inrange(len(board))]for r inrange(len(board)):for c inrange(len(board[0])):if check(0, r, c):returnTruereturnFalse

java：

classSolution{publicbooleanexist(char[][] board,String word){boolean[][] visited =newboolean[board.length][board[0].length];for(int r =0; r < board.length;++r){for(int c =0; c < board[0].length;++c){if(check(board, word,0, visited, r, c)){returntrue;}}}returnfalse;}privatebooleancheck(char[][] board,String word,int idx,boolean[][] visited,int r,int c){if(r <0|| r >= visited.length || c <0|| c >= visited[0].length || visited[r][c]|| board[r][c]!= word.charAt(idx)){returnfalse;}if(idx == word.length()-1){// 完全匹配returntrue;}
        visited[r][c]=true;// 上下左右递归套娃大法if(check(board, word, idx +1, visited, r -1, c)||check(board, word, idx +1, visited, r +1, c)||check(board, word, idx +1, visited, r, c -1)||check(board, word, idx +1, visited, r, c +1)){returntrue;}
        visited[r][c]=false;returnfalse;}}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~