Time Limit Exceeded o with a backtracking solution


  • 0
    E
    class Solution {
    public:
    void setM(vector<vector<bool>>& b, int row, int col) {
        for(int i =0; i < row; i++) {
            vector<bool> temp;
            b.push_back(temp);
            for(int k =0; k < col; k++) {
                b[i].push_back(false);
            }
        }
    }
    bool look(vector<vector<char>>& board, vector<vector<bool>> sol,int row, int col, string word, int index) {
        if(row >= board.size() || row < 0)
            return false;
        if(col > board[0].size() || col < 0)
            return false;
        
        if(sol[row][col])
            return false;
        if(board[row][col] != word[index])
            return false;
        
        sol[row][col]=true;
        
        if(index+1 == word.size())
            return true;
        return look(board, sol,row+1, col, word, index+1) || look(board, sol,row-1, col, word, index+1) || look(board, sol,row, col+1, word, index+1) ||look(board, sol,row, col-1, word, index+1);
        
    }
    
    bool exist(vector<vector<char>>& board, string word) {
        
        if(word.size()<1)
            return true;
        if(board.size()<1)
            return false;
        if (board.size() * board[0].size() < word.size())
            return false;
    
        vector<vector<bool>> sol;
        setM(sol, board.size(), board[0].size());
        
        for(int i =0; i < board.size(); i++) {
            for(int k =0; k < board[0].size(); k++) {
                if(board[i][k]  == word[0]){
                    if(look(board, sol, i, k, 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.