给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board = [ [‘A’,‘B’,‘C’,‘E’], [‘S’,‘F’,‘C’,‘S’], [‘A’,‘D’,‘E’,‘E’] ]
给定 word = “ABCCED”, 返回 true. 给定 word = “SEE”, 返回 true. 给定 word = “ABCB”, 返回 false.
开始一直超时，但是并不知道怎么回事，其他人也是这样就过了。。。后来发现败在了&上，函数参数前加&代表形参引用实参，即直接对实参进行操作。
class Solution { public: bool exist(vector<vector<char>>& board, string word) { int m=board.size(); int n=board[0].size(); vector<vector<bool>> flag(m,vector<bool>(n,false));//全部置为没访问过 for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(search(board,word,i,j,0,flag)) return true; } } return false; } bool search(vector<vector<char>>& board,string &word,int i,int j,int k,vector<vector<bool>> &flag) { if(k==word.length()) return true; if(i<0 || i>=board.size() || j<0 || j>=board[0].size()||flag[i][j]!=false||board[i][j]!=word[k]) return false; flag[i][j]=true;//置为已访问过 bool result=search(board,word,i-1,j,k+1,flag)||search(board,word,i+1,j,k+1,flag)||search(board,word,i,j-1,k+1,flag)||search(board,word,i,j+1,k+1,flag); flag[i][j]=false;// return result; } };给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例:
输入: words = [“oath”,“pea”,“eat”,“rain”] and board = [ [‘o’,‘a’,‘a’,‘n’], [‘e’,‘t’,‘a’,‘e’], [‘i’,‘h’,‘k’,‘r’], [‘i’,‘f’,‘l’,‘v’] ]
输出: [“eat”,“oath”] 说明: 你可以假设所有输入都由小写字母 a-z 组成。
提示:
你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯？ 如果当前单词不存在于所有单词的前缀中，则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作？散列表是否可行？为什么？ 前缀树如何？如果你想学习如何实现一个基本的前缀树，请先查看这个问题： 实现Trie（前缀树）。
class Trie{ public: bool is_str; Trie *next[26]; string strword; Trie() { is_str=false;//是否到一个单词的结尾 memset(next,0,sizeof(next)); strword=""; } void insert(Trie *root,const string word) { Trie *cur=root; for(char w:word) { if(cur->next[w-'a']==NULL) { Trie *newnode=new Trie(); cur->next[w-'a']=newnode; } cur=cur->next[w-'a']; } cur->is_str=true; cur->strword=word; } }; class Solution { private: vector<string> res={}; public: vector<string> findWords(vector<vector<char>>& board, vector<string>& words) { int m=board.size(); int n=board[0].size(); if(m==0||words.size()==0) return res; vector<vector<bool>> visit(m,vector<bool>(n,false));//存储是否访问过 //把所有的单词插入trie树 Trie root; for(string word :words) { root.insert(&root,word); } for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { dfs(board,&root,i,j,visit); } } return res; } void dfs(vector<vector<char>>& board, Trie *root,int i,int j,vector<vector<bool>> &visit) { if(i<board.size()&&i>=0&&j<board[0].size()&&j>=0&&!visit[i][j]) { visit[i][j]=true;//置为访问过 root=root->next[board[i][j]-'a']; if(root) { if(root->is_str)//是一个单词的结尾 { res.push_back(root->strword); root->is_str=false; } //不是的话 dfs(board,root,i+1,j,visit); dfs(board,root,i-1,j,visit); dfs(board,root,i,j+1,visit); dfs(board,root,i,j-1,visit); } visit[i][j]=false; } } };