一个n*m的字母网格grid
,格子中的字母属于26个大写字母。选择某个格子作为起始点,每一步可以移动到上下左右相邻的格子中,这样遍历经过的字母组成了单词(每个格子只能访问一次)。
判断是否能够在网格中找到给定的单词pattern
。
样例:
n=3,m=4 Grid: PACD BGHI MNDC 对于pattern = "DCHGB",返回true。 对于pattern = "PBGNDC", 返回true。 对于pattern = "CIDCB",返回false。
就是LeetCode 的 Word Search。
bool travel(vector<vector<char> >& grid,int x,int y,string& pat,int k); bool exists(vector<vector<char> > &grid, string pattern) { int m=grid.size(); if (m==0) return pattern.empty(); int n=grid[0].size(); for(int i=0;i<m;i++) for(int j=0;j<n;j++) if(travel(grid,i,j,pattern,0)) return true; return false; } bool travel(vector<vector<char> >& grid,int x,int y,string& pat,int k) { if ( k >=pat.size() ) return true; if ( x<0 ||x>=grid.size()||y<0||y>=grid[0].size()) return false; if (pat[k]!=grid[x][y]) return false; char tmp=grid[x][y]; grid[x][y]= '#'; //must not exist in pattern bool ret= travel(grid,x+1,y,pat,k+1)||travel(grid,x-1,y,pat,k+1) ||travel(grid,x,y+1,pat,k+1)||travel(grid,x,y-1,pat,k+1); grid[x][y]=tmp; return ret; }