RE, but works fine on my Mac


  • 0
    B

    RE for input "hot", "dog", ["hot", "dog", "dot"]. I got result 3 on my Mac successfully.

    class Solution {
    public:
        int ladderLength(string beginWord, string endWord, unordered_set<string>& wordDict) {
            int dictSize = wordDict.size();
            vector<unordered_set<string> > close(dictSize+2);
            unordered_set<string> newDict;
            newDict.insert(beginWord);
            close[0] = newDict;
            wordDict.erase(beginWord);
            int lastRound = 0;
            while (!close[lastRound].empty()) {
                newDict.clear();
                for (auto it=close[lastRound].begin(); it!=close[lastRound].end(); it++) {
                    if (linked(*it, endWord)) return lastRound+2;
                    for (auto it_j=wordDict.begin(); it_j!=wordDict.end(); it_j++) {
                        if (linked(*it, *it_j)) {
                           newDict.insert(*it_j);
                           wordDict.erase(*it_j);
                        }
                    }
                }
                lastRound++;
                close[lastRound] = newDict;
            }
            return 0;
        }
    
        int linked(string w1, string w2) {
            bool same = true;
            if (w1.length() != w2.length()) return false;
            for (int i=0; i<w1.length(); i++) {
                if (w1[i] != w2[i]) {
                    if (same) {
                        same = false;
                    } else {
                        return false;
                    }
                }
            }
            return true;
        }
    };

  • 2
    A
    for (auto it_j=wordDict.begin(); it_j!=wordDict.end(); it_j++) {
                    if (linked(*it, *it_j)) {
                       newDict.insert(*it_j);
                       wordDict.erase(*it_j);
                    }
                }
    

    Do not modify container while iterating. Iterator might be invalid after container size changed, depend on compiler implementation.


Log in to reply
 

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