Accepted in 52ms using backtracking


  • 0
    D
    class Solution {
    public:
        int n,m;
        bool vis[100][100];
        int dx[4] = {1,0,-1,0};
        int dy[4] = {0,-1,0,1};
        bool dfs(int x,int y,int depth,vector<vector<char> > &board, string &word){
            if(board[x][y]==word[depth]){
                if(depth == word.length()-1)
                    return true;
                for(int i=0;i<4;i++){
                    int nx = x+dx[i];
                    int ny = y+dy[i];
                    if(nx>=0 && ny>=0 && nx<n && ny<m && !vis[nx][ny]){
                        vis[nx][ny] = true;
                        if(dfs(nx,ny,depth+1,board,word))
                            return true;
                        vis[nx][ny] = false;
                    }
                }
            }
            return false;
        }
        bool check(int x,int y, vector<vector<char> > &board, string &word){
            memset(vis,0,sizeof(vis));
            vis[x][y] = true;
            return dfs(x,y,0,board,word);
        }
        bool exist(vector<vector<char> > &board, string word) {
            n = board.size();
            m = board[0].size();
            for(int i=0;i<n;i++)
                for(int j=0;j<m;j++)
                    if(board[i][j] == word[0]){
                        if(check(i,j,board,word))
                            return true;
                    }
                    
            return false;
        }
    };

Log in to reply
 

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