C++ 9ms Two-way BFS solution


  • 0
    class Solution {
    public:
        int openLock(vector<string>& deadends, string target) {
            int res = 0, trg = stoi(target);
            vector<bool> visited_s(10000, false), visited_e(10000, false);
            for (auto &s : deadends) {
                int n = stoi(s);
                visited_s[n] = visited_e[n] = true;            
            }
            if (visited_s[0]) return -1;
            if (trg == 0) return res;
            queue<int> q_s({0}), q_e({trg});
            visited_s[0] = true; visited_e[trg] = true;
            
            while (!q_s.empty() && !q_e.empty()) {
                if (q_e.size() < q_s.size()) {
                    swap(q_s, q_e);
                    swap(visited_s, visited_e);
                }
                int fringe = q_s.size();   
                res++;
                while(fringe--) {
                    int pass = q_s.front();
                    q_s.pop();
                    int n = pass;
                    for (int i = 0; i < 4; i++) {
                        int diff = pow(10, i);
                        int d = n % 10;
                        n /= 10;
                        int inc = pass + (d == 9 ? -9 * diff : diff);
                        if (!visited_s[inc]) {
                            if (visited_e[inc]) return res;
                            visited_s[inc] = true;
                            q_s.push(inc);
                        }
                        int dec = pass + (d == 0 ? 9 * diff : -diff);
                        if (!visited_s[dec]) {
                            if (visited_e[dec]) return res;
                            visited_s[dec] = true;
                            q_s.push(dec);
                        }
                    }
                }
            }
            return -1;
        }
    };
    

Log in to reply
 

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