Sharing my 24ms C++ solution


  • 0
    T
    class Solution {
    private:
        bool existHelper(vector<vector<char>>& board, string& word, int i, int j, int pos)
        {
            int m = board.size();
            int n = board[0].size();
                
            if(pos == word.length())
                return true;
        
            if(word[pos] != board[i][j])
                return false;
                
            if(pos == word.length()-1 && word[pos] == board[i][j])
                return true;
    
            char c = board[i][j];
            board[i][j] = '*';
            bool r = false;
            if(i-1>=0 && existHelper(board, word, i-1, j, pos+1))
            {
                r = true;
                goto final;
            }
            if(i+1<m && existHelper(board, word, i+1, j, pos+1))
            {
                r = true;
                goto final;
            }
            if(j-1>=0 && existHelper(board, word, i, j-1, pos+1))
            {
                r = true;
                goto final;
            }
            if(j+1<n && existHelper(board, word, i, j+1, pos+1))
            {
                r = true;
                goto final;
            }
         
    final:
            board[i][j] = c;
            return r;
        }
    public:
        bool exist(vector<vector<char>>& board, string& word) {
            int m = board.size();
            int n = board[0].size();
            int i, j;
    
            bool r = false;
            for(i=0; i<m; i++)
                for(j=0; j<n; j++)
                {
                    if(existHelper(board, word, i, j, 0))
                    {
                        return true;
                    }
                }
            return r;
        }
    };

Log in to reply
 

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