79.word-search.md

79. 单词搜索

1. 描述

   • 给定一个二维网格和一个单词，找出该单词是否存在于网格中。

   • 单词必须按照字母顺序，通过相邻单元格（水平/垂直相邻）内的字母构成。

   • 同一个单元格内的字母不允许重复使用。

2. 示例:

   board =
   [
     ['A','B','C','E'],
     ['S','F','C','S'],
     ['A','D','E','E']
   ]
   
   给定 word = "ABCCED", 返回 true
   给定 word = "SEE", 返回 true
   给定 word = "ABCB", 返回 false
   

3. 实现（注意主函数exist里双重循环里的判断条件，别写错！）

   class Solution {
   public:
   	bool dfs(vector<vector<char>>& board, string& word, vector<vector<int>>& visit, int index, int i, int j){       
   		// 如果已经访问
   		if(visit[i][j])
   			return false;
   		
   		// 不匹配，剪枝
   		if(word[index] !=  board[i][j])
   			return false;
   		
   		// 单词最后一个字母也匹配，
   		// 说明 word 存在于 网格board 中。
   		if(index == word.size()-1)
   			return true;
   		
   		// 访问
   		visit[i][j] = 1;
   		
   		// 回溯
   		if( i+1<board.size()     && dfs(board, word, visit, index+1, i+1, j))
   			return true;
   		if( j+1<board[0].size()  && dfs(board, word, visit, index+1, i, j+1)) 
   			return true;
   		if( i-1>=0               && dfs(board, word, visit, index+1, i-1, j)) 
   			return true;
   		if( j-1>=0               && dfs(board, word, visit, index+1, i, j-1))  
   			return true;
   		
   		// 取消访问
   		visit[i][j] = 0;
   		
   		// 没有搜索到结果
   		return false;
   	}
   	bool exist(vector<vector<char>>& board, string word) {
   		vector<vector<int>>visit(board.size(), vector<int>(board[0].size(), 0));
   		int i, j;
   		for(i=0; i<board.size(); i++){
   			for(j=0; j<board[0].size(); j++){
   				
   				// 注意，不要写成 下面这样：
   				// return dfs(board, word, visit, 0, i, j)
   
   				if (dfs(board, word, visit, 0, i, j))
   					return true;
   			}
   		}
   		return false;
   	}
   };