C++ Concise, Clean Solution Using DFS


#1

int dfs(vector &A, int i, int j, int k, string B)
{
if(k >= B.length())
{
return 1;
}
if(i<0 || i>=A.size() || j<0 || j>=A[0].size() || A[i][j]!=B[k])
{
return 0;
}

if(
    dfs(A,i,j+1,k+1,B) ||
    dfs(A,i,j-1,k+1,B) ||
    dfs(A,i+1,j,k+1,B) ||
    dfs(A,i-1,j,k+1,B)
)
{
    return 1;
}
else
{return 0;}

}

int Solution::exist(vector &A, string B) {

if(A.size() == 0 || B.length() == 0)
{
    return 0;
}
int flag = 0;

for(int i=0;i<A.size();i++)
{
    for(int j=0;j<A[i].size();j++)
    {
        if(A[i][j] == B[0])
        {
            flag = dfs(A,i,j,0,B);
            if(flag == 1)
            {return 1;}
        }
    }
}
return flag;

}