# My C++ 12ms backtracking solution easy to understand, beats 99.36% of cppsubmissions.

• ``````class Solution {
public:
bool existHelper( vector<vector<char>>& board, int& m, int& n, string& word, int boardI, int boardJ, int wordInx, vector<vector<bool>>& isSearched ){
if(wordInx==word.length())
return true;
// right
if( boardJ+1<n && board[boardI][boardJ+1]==word[wordInx] && isSearched[boardI][boardJ+1]==false ){
isSearched[boardI][boardJ+1] = true;
if( existHelper(board,m,n,word,boardI,boardJ+1,wordInx+1,isSearched) )
return true;
isSearched[boardI][boardJ+1] = false;
}
// down
if( boardI+1<m && board[boardI+1][boardJ]==word[wordInx] && isSearched[boardI+1][boardJ]==false ){
isSearched[boardI+1][boardJ] = true;
if( existHelper(board,m,n,word,boardI+1,boardJ,wordInx+1,isSearched) )
return true;
isSearched[boardI+1][boardJ] = false;
}
// left
if( boardJ-1>=0 && board[boardI][boardJ-1]==word[wordInx] && isSearched[boardI][boardJ-1]==false ){
isSearched[boardI][boardJ-1] = true;
if( existHelper(board,m,n,word,boardI,boardJ-1,wordInx+1,isSearched) )
return true;
isSearched[boardI][boardJ-1] = false;
}
// up
if( boardI-1>=0 && board[boardI-1][boardJ]==word[wordInx] && isSearched[boardI-1][boardJ]==false ){
isSearched[boardI-1][boardJ] = true;
if( existHelper(board,m,n,word,boardI-1,boardJ,wordInx+1,isSearched) )
return true;
isSearched[boardI-1][boardJ] = false;
}
return false;
}
bool exist(vector<vector<char>>& board, string word) {
int m = board.size();
int L = word.length();
if( L==0 )
return true;
if( m==0 )
return false;
int n =  board[0].size();

// preprocess
vector<int> letterCnt(256,0);
for( int i = 0; i<m; i++ ){
for( int j = 0; j<n; j++ ){
letterCnt[board[i][j]]++;
}
}
for( int i = 0; i<L; i++ ){
letterCnt[word[i]]--;
}
for( int i = 0; i<256; i++ ){
if( letterCnt[i]<0 )
return false;
}

vector<vector<bool>> isSearched(m,vector<bool>(n,false));
int startJ = 0;
for( int i = 0; i<m; i++ ){
for( int j = 0; j<n; j++ ){
if( board[i][j]==word[0] ){
isSearched[i][j] = true;
if( existHelper(board,m,n,word,i,j,1,isSearched) )
return true;
isSearched[i][j] = false;
}
}
}
return false;
}
};``````

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