Can someone help me? Why can't I pass this test case


  • 0
    D

    I am using DFS and pruning. I failed the following test case:

    Input: ["ABCDE","TSRQF","MNOPG","LKJIH"], "ABCDEFGHIJKLMNOPQRST"
    Output: false
    Expected: true

    But I copied my code and tested the same test case on my own computer and the result was true. I have no idea why Leetcode online judge got my result as false...

    The following is my code:

    	bool check(int row, int col, vector<vector<char> > &board, string word, vector<vector<bool> > &status) {
    	if (!status[row][col] && board[row][col] == word[0]) {
    		status[row][col] = true;
    		if (word.size() == 1) {
    			return true;
    		}else {
    			if (row > 0) {
    				if (check(row-1, col, board, word.substr(1), status)) {
    					
    					return true;    
    				}
    			}
    			if (row < board.size() - 1) {
    				if (check(row+1, col, board, word.substr(1), status)) {
    
    					return true;
    				};
    			}
    			if (col > 0) {
    				if (check(row, col-1, board, word.substr(1), status)) {
    				   
    					return true;
    				};
    			}
    			if (col < board[0].size() - 1) {
    				if (check(row, col+1, board, word.substr(1), status)) {
    				 
    					return true;
    				}
    			}
    			status[row][col] = false;
    			cout << "return false!!! row = " << row << ", col = " << col << endl;	
    		}
    		
    	}
    	return false;
    }
    
    bool exist(vector<vector<char> > &board, string word) {
    	vector<vector<bool> >visited (board.size(), vector<bool> (false, board[0].size()));
    	for (int i = 0; i < board.size(); ++i) {
    		for (int j = 0; j < board[0].size(); ++j) {
    			if (check(i, j, board, word, visited)) {
    				return true;
    			}
    		}
    	}
    	return false;
    	
    }
    

    Thanks!!!


  • 0
    W

    I don't know whether your machine has some error. The code you pasted exists syntax error and even can't give a result. Of course, it can't pass the OJ...

    Here, ; is reduncdant.

    if (check(row+1, col, board, word.substr(1), status)) {
        return true;
    };
    

    And this one,

    vector<vector<bool> >visited (board.size(), vector<bool> (false, board[0].size()))
    

    Are you kidding me?

    Except these mistakes, the code is all right. Here is the code been modified and have passed the OJ.

    class Solution {
    public:
        bool check(int row, int col, vector<vector<char> > &board, string word, vector<vector<bool> > &status) {
            if (!status[row][col] && board[row][col] == word[0]) {
                status[row][col] = true;
                if (word.size() == 1) {
                    return true;
                }else {
                    if (row > 0) {
                        if (check(row-1, col, board, word.substr(1), status)) {
        
                            return true;    
                        }
                    }
                    if (row < board.size() - 1) {
                        if (check(row+1, col, board, word.substr(1), status)) {
        
                            return true;
                        };
                    }
                    if (col > 0) {
                        if (check(row, col-1, board, word.substr(1), status)) {
        
                            return true;
                        }
                    }
                    if (col < board[0].size() - 1) {
                        if (check(row, col+1, board, word.substr(1), status)) {
        
                            return true;
                        }
                    }
                    status[row][col] = false;
                }
        
            }
            return false;
        }
        bool exist(vector<vector<char> > &board, string word) {
            vector<vector<bool> >visited (board.size(), vector<bool> (board[0].size(), false));
            for (int i = 0; i < board.size(); ++i) {
                for (int j = 0; j < board[0].size(); ++j) {
                    if (check(i, j, board, word, visited)) {
                        return true;
                    }
                }
            }
            return false;
        
        }
    };

Log in to reply
 

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