C++ straight-forward BFS solution, no TLE!


  • 0
    M
        int openLock(vector<string>& deadends, string target) {
            int step=0;
            unordered_set<string> dupe;
            for(int i=0;i<deadends.size();i++) dupe.insert(deadends[i]);
            if(dupe.find("0000")!=dupe.end()) return -1;
            if(dupe.find(target)!=dupe.end()) return -1;
            queue<string> q;
            q.push("0000");
            while(!q.empty()) {
                step++;
                int size=q.size();
                for(int j=0;j<size;j++) {
                    string s=q.front();
                    q.pop();
                    for(int i=0;i<4;i++) {
                        char c=s[i];
                        s[i]++;
                        if(s[i]>'9') s[i]='0';
                        if(s==target) return step;
                        if(dupe.find(s)==dupe.end()) q.push(s);
                        dupe.insert(s);
                        s[i]=c-1;
                        if(s[i]<'0') s[i]='9';
                        if(s==target) return step;
                        if(dupe.find(s)==dupe.end()) q.push(s);
                        dupe.insert(s);
                        s[i]=c;
                    }
                }
            }
            return -1;
        }

Log in to reply
 

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