首页 > 代码库 > [LeetCode] Word Search
[LeetCode] Word Search
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example, Given board =
[ ["ABCE"], ["SFCS"], ["ADEE"]]
word = "ABCCED", -> returns true, word = "SEE", -> returns true, word = "ABCB", -> returns false.
class Solution {public: bool exist(vector<vector<char> > &board, string word) { if(board.size()==0) return false; if(word.size()==0) return true; vector<bool> used0(board[0].size(),false); vector<vector<bool> > used(board.size(),used0);//used标记每个元素是否已经使用过 for(int i=0;i<board.size();i++) for(int j=0;j<board[0].size();j++) { if( DFS(board,word,i,j,0,used)) return true; } return false; }//end existprivate: bool isInboard(vector<vector<char> > &board,int row,int col) { if(row<0 || row>=board.size()) return false; if(col<0 || col>=board[0].size()) return false; return true; } bool DFS(vector<vector<char> > &board,string &word,int row,int col,int n,vector<vector<bool> >&used)//n是word中的序号，row和col是board中的序号 { if(n == word.size()) return true; if(isInboard(board,row,col)) { if(used[row][col]==false && word[n]==board[row][col]) { used[row][col]=true; if(DFS(board,word,row+1,col,n+1,used)) { return true; } else if(DFS(board,word,row-1,col,n+1,used)) { return true; } else if(DFS(board,word,row,col+1,n+1,used)) { return true; } else if(DFS(board,word,row,col-1,n+1,used)) { return true; } used[row][col]=false;//如果此条路没走通，那此处的used还是原先的false，可供下一次的深度优先搜索使用 }//end if }//end if return false; } };
方法：使用深度优先搜索算法（DFS）。
特点是：第一个搜索开始点可能有若干个(即满足s[0]==board[i][j]的i和j会有若干个），找到开始点（i，j）后，沿着开始点持续往下搜索直到成功或失败，如果失败，找下一个可以满足s[0]]==board[i][j]的（i，j）点继续搜索。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。