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;
     }
};