要求
- 给定一个二维平面的字母和一个单词,从一个字母出发,横向或纵向连接二维平面上的其他字母
- 同一位置的字母只能使用一次
示例
- board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ]
- 给定 word = "ABCCED",返回 true
- 给定 word = "SEE",返回 true
- 给定 word = "ABCB",返回 false
思路
实现
- board:要查找的区域
- word:要查找的字符串
- index:要查找字符串中的第几个字符
- startx,starty:查找起始位置
- inArea():判断是否在查找区域内
- visited:记录是否访问过
- 24-26:递归逻辑,先写好这段,再扩充其他部分
- 15-16:终止条件
1 class Solution { 2 3 private: 4 int d[4][2] = {{-1,0},{0,1},{1,0},{0,-1}}; 5 int m,n; 6 vector<vector<bool>> visited; 7 8 bool inArea( int x , int y ){ 9 return x >= 0 && x < m && y >= 0 && y< n; 10 } 11 // 从board[startx][starty]开始,寻找word[index...word.size()] 12 bool searchWord( const vector<vector<char>> &board, const string& word, int index, 13 int startx, int starty){ 14 15 if( index == word.size() - 1 ) 16 return board[startx][starty] == word[index]; 17 18 if(board[startx][starty] == word[index] ){ 19 visited[startx][starty] = true; 20 // 从startx,starty出发,向四个方向寻找 21 for( int i = 0 ; i < 4 ; i ++ ){ 22 int newx = startx + d[i][0]; 23 int newy = starty + d[i][1]; 24 if( inArea(newx,newy) && !visited[newx][newy] && 25 searchWord( board, word, index+1, newx, newy )) 26 return true; 27 } 28 visited[startx][starty] = false; 29 } 30 return false; 31 } 32 public: 33 bool exist(vector<vector<char>>& board, string word) { 34 35 m = board.size(); 36 assert( m > 0); 37 n = board[0].size(); 38 39 visited = vector<vector<bool>>(m, vector<bool>(n, false)); 40 41 for( int i = 0 ; i < board.size() ; i ++) 42 for( int j = 0 ; j < board[i].size() ; j ++ ) 43 if(searchWord( board, word, 0, i, j ) ) 44 return true; 45 46 return false; 47 } 48 };