Why runtime error?


  • 0
    Y

    Could anybody tell me why I got Runtime Error?

    This is a simple BFS code, and it runs well on my linux machine. However, I got an runtime error for this test case:
    Last executed input: "hot", "dog", ["hot","cog","dog","tot","hog","hop","pot","dot"]

    it seems that the "dict.erase()" is wrong?

    bool canReach(string a, string b) {
        if (a == b) return false;
        int n = a.length();
        int c = 0;
        for (int i = 0; i < n; ++i) {
            if (a[i] != b[i]) {
                c++;
                if (c > 1) return false;
            }
        }
        return (c == 1);
    }
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        if (dict.empty()) return 0;
        if (start.empty() || end.empty()) return 0;
        if (start.length() != end.length()) return 0;
        dict.insert(start);
        dict.insert(end);
        
        queue<unordered_set<string>::iterator> q;
        q.push(dict.find(start));
        q.push(dict.end());
        int n = start.length();
        
        int h = 0;
        while (q.size() > 1) {
            unordered_set<string>::iterator t = q.front();
            q.pop();
                
            if (t == dict.end()) { h++; q.push(dict.end()); continue;}
            if (*t == end) return h;
            string tmp(*t);
            dict.erase(t);
            for (unordered_set<string>::iterator it = dict.begin(); it != dict.end(); ++it) {
                if (canReach(tmp, *it)) {
                    q.push(it);
                }
            }
        }
        
        return h;
    }

  • 0
    S

    Yes, might be dict.erase(). Since it is passed by reference, not quite sure if solution modify it will influence the judger.


  • 0
    Y

    Thanks a lot.

    I know what happened now.

    i. e.

    start = "hit"
    end = "cog"
    dict = ["hot","dot","dog","lot","log"]

    Then we have two transformations: "hit" -> "hot" -> "dot" -> "dog" -> "cog".
    "hit"->"hot"->"lot"->"log"->"cog".

    Notice that when we process "hot", we push "dot" and "lot" into the queue. Then when we process "dot", we also push its 'neighbour', namely "lot", into the queue. And there are two "lot" in the queue now. Then the program will try to erase the "lot" twice. That's why I got a runtime error.


  • 0
    S

    why not create another checker by yourself to save the visited word, not delete from dict.


  • 0
    Y

    Hi Shangrila, I then use another method for deletion. Here is my code.

    int ladderLength(string start, string end, unordered_set<string> &dict)
    {
    if (dict.empty()) return 0;
    if (start.empty() || end.empty()) return 0;
    if (start.length() != end.length()) return 0;
    dict.insert(end);

        queue<string> q;
        q.push(start);
        q.push("");
        int n = start.length();
        
        int h = 1;
        while (q.size() > 1) {
            string tmp = q.front();
            q.pop();
                
            if (tmp.empty()) { h++; q.push(""); continue;}
            
            for (int i = 0; i < n; ++i) {
                for (char c = 'a'; c <= 'z'; ++c) {
                    string next(tmp);
                    next[i] = c;
                    if (next == end) return h + 1;
                    if (next != tmp && dict.find(next) != dict.end()) {
                        q.push(next);
                        dict.erase(next);
                    }
                }
            }
        }
        
        return 0;
    }

Log in to reply
 

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