# WORD-SEARCH leetcode Solution - Correct, Optimal and Working

``````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;

}
};
``````