AC in 896 ms, C++ code, is this a stupid method or something


  • -4
    M
    bool exist(vector<vector<char> > &board, string word) {
            if(word.size() == 0) return true;
            if(board.size() == 0) return false;
            bool result = false;
            for(int i = 0; i < board.size(); i++){
                for(int j = 0; j < board[i].size();j++){
                    if(board[i][j] == word[0]){
                        vector<vector<char> > vec(board);   //every search use a new vector
                        vec[i][j] = '#';      //change the char to special one 
                        result = exist(vec, i, j, word, 1);
                        if(result) return true;
                    }
                }
            }
            return result;
        }
        bool exist(vector<vector<char>> &board, int i, int j, string word, int index){
            if(index == word.size()) return true;
            bool one=false,two=false,three=false,four=false;   // four direction search result
            if(i+1 < board.size() && board[i + 1][j] == word[index]){
                vector<vector<char>> vec(board);
                vec[i+1][j] = '#';
                one = exist(vec, i+1, j, word, index + 1);
            }
            if(one){
                return true;
            }
            if(i-1 >= 0 && board[i-1][j] == word[index]){
                vector<vector<char>> vec(board);
                vec[i-1][j] = '#';
                two = exist(vec, i-1, j, word, index + 1);
            }
            if(two){
                return true;
            }
            if(j+1 < board[i].size() && board[i][j+1] == word[index]){
                vector<vector<char>> vec(board);
                vec[i][j+1] = '#';
                three = exist(vec, i, j+1, word, index + 1);
            }
            if(three){
                return true;
            }
            if(j - 1 >=0 && board[i][j-1] == word[index]){
                vector<vector<char>> vec(board);
                vec[i][j-1] = '#';
                four = exist(vec, i, j-1, word, index + 1);
            }
            return four;
        }``
    

    could someone tell me the DFS iterative methods' time cost


Log in to reply
 

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