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


  • 0
    C
    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;
        }
    };

Log in to reply
 

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