回溯法:
/** 图搜索: 二维搜索起始点: 终止条件: 第一次找到该单词:当k>=word.size(),说明前k个字母已经全部找到,令res=true;return; 剪枝条件: 该方向的词与word对应的字母不相等:说明当前搜索分支不会有正确答案; 已经找到该单词(即res==true),说明在某一分支中已经找到了正确的字符串,当前分支不必再进行搜索; 新的字母坐标不在board中,或者已经被访问过; **/ class Solution { public: vector<vector<int>>dirs={{-1,0},{0,1},{1,0},{0,-1}}; bool exist(vector<vector<char>>& board, string word) { bool res=false; int m=board.size(); if(m==0) return false; int n=board[0].size(); if(n==0&&word.size()==0) return true; vector<vector<int>> visit(m,vector(n,0)); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(board[i][j]==word[0]) dfs(board,word,visit,res,i,j,0); if(res==true) return res; } } return res; } void dfs(vector<vector<char>>& board,string &word,vector<vector<int>>&visit,bool& res,int i,int j,int k){ //递归终点 if(k>=word.size()){ res=true;return; } //剪枝条件 if(i<0||i>=board.size()||j<0||j>=board[0].size()||board[i][j]!=word[k]||visit[i][j]==1||res==true) return; visit[i][j]=1; for(auto dir:dirs){ dfs(board,word,visit,res,i+dir[0],j+dir[1],k+1); } visit[i][j]=0; } };