Leetcode oj and visual studio gives different result for same test case


  • 1
    R
    class Solution {
    
    public:
    	bool wordBreak(string s, unordered_set<string> &dict) {
    	    if (dict.empty()) return false;
    		//pos[i] = j, then s[j..i) can break
    		vector<unsigned int> pos(s.size()+1, UINT_MAX);
    		for (auto it = dict.begin(); it != dict.end(); ++it) {
    			if (it->size() <= s.size()) {
    				size_t p = s.find(*it);
    				while (p != string::npos) {
    
    					pos[p+it->size()] = min(p, pos[p]);
    
    					p = s.find(*it, p+1);
    				}
    			}
    		}
    		return pos.back() == 0;
    	}
    };
    

    My idea is: Think of s as connected by words in dict. Vector `pos' is used to record the already connected part of s.
    If pos[i] is j, it means substring of s start from index j(included) to i(excluded) is connected by words in dict. So finally we only need to check whether pos[s.size()](the end) equals 0(the start). If it is, then the whole string s is connected.

    My problem is: the OJ's output is different from the output if I ran the same test case as follows.

    The OJ says:

    Input: "ab", ["a","b"]

    Output: false

    Expected: true

    But when run in visual studio, given the case above, this program returns true, as is expected.

    The program doesn't work at all. And my problem is not about the correctness of my program. My problem is why the OJ and Visual Studio gives me different results for the same program and the same test case.


  • 0
    S

    LeetCode judger runs code once for all test case.

    vector<unsigned int> pos(s.size()+1, UINT_MAX);

    I believe this pos should be clear every time go to this function.

    However, it would be better tell more about your idea and code to figure out what is exactly incorrect.


  • 0
    R

    I described my idea. `pos' is just a local variable to the function. I don't think it's the problem. There may be something wrong with the OJ. I ran code previously accepted for some other problem but get a complie error!


  • 0
    S

    Appreciate your update.

    But if you add pos.clear(), the failed case becomes

    Input:	"a", ["a"]
    Output:	false
    Expected:	true
    

    Do not blame OJ too much. I admit sometimes OJ does not give the correct error message, when code goes Runtime Error or Wrong Answer. But, usually such situation are caused by underlying bug in people's code.


  • 0
    R

    `pos' would be created when entering this function and destroyed when leaving the function according to the C++ standard. There's no difference whether it's cleared or not when entering this function.
    The OJ obviously don't work the same as before. I do not blame. I state the fact. By the way, OJ is also software written by human.


  • 0

    If you run through the code step by step for the case "ab", ["a","b"], then pos[1] = 0 and pos[2] = 1, pos.back() = pos[2] = 1, which is ≠ 0. Agree?

    I understand the frustration you are going through when debugging your program, but remember during an interview you do not have such luxury of knowing the failing test case! I found the most effective way to practice your debugging skills is to work on a paper going through your code step by step. Fortunately, this test case is simple so it can be worked out in a matter of minutes.


  • 0

    To correct what @Shangrila had mentioned, you do not have to worry about clearing your variables, as a brand new Solution instance is being created for each test case. You do have to worry when you declare a static variable though.


  • 0
    R

    Have you actually run the program? pos[1] = 0, pos[2] = min(1, pos[1]) = 0!

    The program is buggy, but not for the case you stated.

    And my problem is not about the correctness of my program. My problem is why the OJ and Visual Studio gives me different results for the same program and the same test case!


  • 0

    You are assuming that unordered_set guarantees the ordering of elements while you are iterating it. It doesn't.

    Quoting here: Notice that an unordered_set object makes no guarantees on which specific element is considered its first element


  • 0
    R

    My question is not the correctness of my program. It's not correct even if set is ordered.


Log in to reply
 

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