本文共 1191 字，大约阅读时间需要 3 分钟。

解题思路：

* BFS + DFS

* 每次找一个字符，使用BFS（上，下，左，右）

* 第一个字符的位置通过遍历整个board得到

* 从第i个找第i+1个只能查找周围没有被使用过的，用DFS

* 用数组标记每个位置是否已被使用

class Solution {public:       bool exist(vector
   
    
     >& board, string word) {        row = board.size();        if(row == 0) return false;        col = board[0].size();        vector
     
      
        > used(row,vector
       
        (col,false));        found = false;               for(int i = 0; i < row; i++){ //遇到一个很奇葩的问题，当把i，j定义在for外面的时候，一直wrong answer            for(int j = 0; j < col; j++){                helper(board,used,word,0,i,j);            }        }        return found;    }    void helper(vector
        
         
           >& board,vector
          
           
             >& used,string& word,int index,int i,int j){ if(found || (word[index] != board[i][j]) ){ return; } if(index == (word.size() - 1)){ found = true; return; } used[i][j] = true; if( (i > 0) && !used[i-1][j]) helper(board,used,word,index+1,i-1,j); if( (i < row - 1) && !used[i+1][j]) helper(board,used,word,index+1,i+1,j); if( (j > 0) && !used[i][j-1]) helper(board,used,word,index+1,i,j-1); if( (j < col -1) && !used[i][j+1] ) helper(board,used,word,index+1,i,j+1); used[i][j] = false; return; } private: bool found; int row,col;};
           
          
         
        
       
      
     
    
   

转载地址：http://tmspi.baihongyu.com/