题目描述
给定一个二维网格和一个单词,找出该单词是否存在于网格中。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =[ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']]给定 word = "ABCCED", 返回 true.给定 word = "SEE", 返回 true.给定 word = "ABCB", 返回 false.
解题思路
本题可用回溯法来求解。定义一个访问数组初始全部置为0,并定义当前路径长度初始置0,从矩阵第一个字符开始遍历:
- 从当前字符出发,若与字符串对应路径长度的字符相等,就分别向上下左右走一步,并把当前字符访问数组置1,路径长度加1;
- 若当前字符走到了字符串末尾,说明存在一条路径与字符串相等,返回true;
- 若当前字符出发的各条路径都不能找到一条路径与字符串相等,则向当前路径上一步回溯,并把当前字符访问数组置0,路径长度减1
代码
1 class Solution { 2 public: 3 bool exist(vector>& board, string word) { 4 if(board.empty()||word=="") 5 return false; 6 int rows=board.size(); 7 int cols=board[0].size(); 8 for(int i=0;i > visit(rows,vector (cols,false));11 if(find(visit,board,word,0,i,j))12 return true;13 }14 }15 return false;16 }17 bool find(vector > &visit, vector >& board, string word, int idx, int row, int col){18 if(idx==word.size())19 return true;20 int rows=board.size();21 int cols=board[0].size();22 if(row =0&&col =0&&!visit[row][col]&&board[row][col]==word[idx]){23 visit[row][col]=true;24 bool hasPath=find(visit,board,word,idx+1,row+1,col)||find(visit,board,word,idx+1,row,col+1)||25 find(visit,board,word,idx+1,row-1,col)||find(visit,board,word,idx+1,row,col-1);26 if(!hasPath)27 visit[row][col]=false;28 else29 return true;30 }31 return false;32 }33 };