Lang: C++; Complexity[Time,Space]:[O(m*n*k), size of recursive function stack]


#1

Title Help: For given array of size m x n and given string of size k.
Idea: Traverse through each cell of the array. If any cell’s value matches with the starting character of the given string, start dfs from that cell matching every character of string at every step. Report any mismatch by returning false.

inline bool isSafe(int x,int y,vector<string> &A) {
    return (0<=x && x<A.size() && 0<=y && y<A[0].size());
}
bool hasWord(vector<string>&A, string&B, int r, int c, int i=0) {
    if(!isSafe(r,c,A)) 
        return 0;
    if(i == B.size()-1) 
        return (A[r][c]==B[i]);
    if(A[r][c] == B[i])
        return hasWord(A,B,r+1,c,i+1)||hasWord(A,B,r-1,c,i+1)||hasWord(A,B,r,c+1,i+1)||hasWord(A,B,r,c-1,i+1);
    return 0;
}
int Solution::exist(vector<string> &A, string B) {
    for(int r=0; r<A.size(); r++)
        for(int c=0; c<A[0].size(); c++)
            if(A[r][c]==B[0] && hasWord(A,B,r,c)) return 1;
    return 0;
}