Clear and simple recusive solution on c++ (72ms)


  • 0
    K
    class Solution {
    public:
        bool check(vector<vector<char>> & board, int i, int j , vector<vector<int>> & mark, string word, int pos ) {
            if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size()) {
                return false;
            }
            
            if (mark[i][j] == 1) {
                return false;
            }
            
            if (board[i][j] == word[pos] ) {
                if (pos == word.size() -1 )
                    return true;
                else {
                    mark[i][j] = 1;
                    if (check(board, i, j+1, mark, word, pos+1)) return true;
                    if (check(board, i, j-1, mark, word, pos+1)) return true;
                    if (check(board, i+1, j, mark, word, pos+1)) return true;
                    if (check(board, i-1, j, mark, word, pos+1)) return true;
                    
                    mark[i][j] = -1;
                    
                    return false;
                }
                
            } else {
                return false;
            }
        }
    
        bool exist(vector<vector<char>>& board, string word) {
         
            vector< vector<int> > mark;
            for (int i = 0; i < board.size(); i++) {
                vector<int> m;
                for (int j = 0; j < board[i].size(); j++) {
                    m.push_back(-1);
                }
                mark.push_back(m);
            } 
            
            for (int i = 0; i < board.size(); i++) {
                for (int j = 0; j < board[i].size(); j++) {
                    if (check(board, i, j, mark, word, 0)) {
                        return true;
                    }
                }
            }
            
            return false;
            
        }
    };

Log in to reply
 

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