class Solution {
public:
int ** visited;
const char * str;
int row = 0 , col = 0;
int nx[4] = {-1,1,0,0};
int ny[4] = {0,0,-1,1};
bool issafe( int x, int y ) {
if( x >= 0 && x < row && y >= 0 && y < col ) {
return true;
}
return false;
}
bool check( vector< vector<char> > &board, int i, int j, const char * str ) {
if( visited[i][j] == 1 ) {
return false;
}
if( board[i][j] == *str && *(str+1) == '\0' ) {
return true;
}
visited[i][j] = 1;
if( board[i][j] == *str ) {
for( int k = 0 ; k < 4 ; k++ ) {
int newx = i + nx[k];
int newy = j + ny[k];
if( issafe(newx,newy) ) {
bool temp = check(board,newx,newy,str+1);
if( temp == true ) {
return true;
}
}
}
}
visited[i][j] = 0;
return false;
}
bool exist(vector<vector<char> > &board, string word) {
str = word.c_str();
row = board.size();
col = board[0].size();
visited = (int **) calloc(sizeof(int *) , row);
for( int i = 0 ; i < row ; i++ ) {
visited[i] = (int *) calloc(sizeof(int) , col);
}
for( int i = 0 ; i < row ; i++ ) {
for( int j = 0 ; j < col ; j++ ) {
if( board[i][j] == str[0] ) {
bool ans = check(board,i,j,str);
if( ans == true ) {
return true;
}
}
}
}
return false;
}
};
System Design Masterclass
A masterclass that helps you become great at designing scalable, fault-tolerant, and highly available systems.
1000+ learners
Details →Redis Internals
Learn internals of Redis by re-implementing some of the core features in Golang.
46+ learners
Details →