要求

• 给定一个二维平面的字母和一个单词，从一个字母出发，横向或纵向连接二维平面上的其他字母
• 同一位置的字母只能使用一次

示例

• 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> 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> &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>& board, string word) {
  34
  35 m = board.size();
  36 assert( m > 0);
  37 n = board[0].size();
  38
  39 visited = vector>(m, vector(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 };