1. 079

word search

2. 算法

dfs:O$$(m^2n^2)$$

• 类似迷宫，递归回溯

• 使用辅助数组记录走过的位置，防止一个位置被使用多次

3.代码

class Solution{

private:

    bool dfs(vector<vector<char> >&board,int x,int y,string word,int idx,vector<vector<bool> > &vis){

        if(idx==word.length())

            return true;

        if(x<0||x>=board.size()||y<0||y>=board[0].size()||

        vis[x][y]||board[x][y]!=word[idx])

            return false;

        vis[x][y]=true;



        bool ret=

                dfs(board,x+1,y,word,idx+1,vis)||

                dfs(board,x-1,y,word,idx+1,vis)||

                dfs(board,x,y+1,word,idx+1,vis)||

                dfs(board,x,y-1,word,idx+1,vis);

        vis[x][y]=false;

        return ret;

     }

public:

    bool exist(vector<vector<char> >& board,string word){

        if(board.empty()||board[0].empty())

            return word==" ";

        int n=board.size(),m=board[0].size();

        vector<vector<bool> > vis(n,vector<bool>(m,false));



        for(int i=0;i<n;i++)

            for(int j=0;j<m;j++)

                if(dfs(board,i,j,word,0,vis))

                    return true;

        return false;

     }

};