Simple DFS Solution without explanation in C++(6ms)


  • 0
    O

    class Solution {
    public:
    int n,m;
    int cnt[333];
    int dx[4] = {0,1,0,-1};
    int dy[4] = {1,0,-1,0};
    bool isok(int cx,int cy)
    {
    return cx >= 0 && cx < n && cy >= 0 && cy < m;
    }
    bool dfs(int cx,int cy,int dp,int len,vector<vector<char> >& board,string& word,vector<vector<bool> >&flag)
    {

        if(board[cx][cy] != word[dp])
            return false;
        if(dp == len - 1)
            return true;
        for(int i = 0;i < 4;++ i)
        {
            int tx = cx + dx[i];
            int ty = cy + dy[i];
            if(isok(tx,ty) && !flag[tx][ty]){
                flag[tx][ty] = true;
                if(dfs(tx,ty,dp + 1,len,board,word,flag))
                    return true;
                flag[tx][ty] = false;
            }
        }
        return false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        n = board.size();
        if(!n)
            return false;
        m = board[0].size();
        memset(cnt,0,sizeof(cnt));
        for(int i = 0;i < n;++ i)
            for(int j = 0;j < m;++ j)
                cnt[board[i][j]] ++;
        int len = word.size();
        if(!len)
            return false;
        for(int i = 0;i < len;++ i){
            cnt[word[i]] --;
            if(cnt[word[i]] < 0)
                return false;
        }
        vector<vector<bool> >flag(n,vector<bool>(m,false));
        for(int i = 0;i < n;++ i){
            for(int j = 0;j < m;++ j){
                flag[i][j] = true;
                if(dfs(i,j,0,len,board,word,flag))
                    return true;
                flag[i][j] = false;
            }
        }
        return false;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.