C++, BFS + Hash Array, 33 ms


  • 0
    Z
    class Solution {
    public:
        int openLock(vector<string>& deadends, string target) {
            if (target == "0000") return 0;
            int N = 10000;
            int dis[N] = {};
            for (string& s: deadends) 
                dis[stoi(s)] = 1;
            if (dis[0] == 1) return -1;
            dis[0] = 1;
            queue<int> myq;
            myq.push(0);
            int tar = stoi(target), step = 0;
            while (!myq.empty()) {
                int sz = myq.size();
                step++;
                for (int i = 0; i < sz; i++) {
                    int key = myq.front();
                    myq.pop();
                    vector<int> adj = getNext(key);
                    for (int i : adj) {
                        if (i == tar) return step;
                        if (dis[i] == 0) {
                            myq.push(i);
                            dis[i] = 1;
                        }
                    }
                }
            }
            return -1;
        }
    private:
        vector<int> getNext(int key) {
            vector<int> ans;
            for (int i = 10; i <= 10000; i *= 10) {
                ans.push_back(key/i*i + (key%i+i/10)%i);
                ans.push_back(key/i*i + (key%i+i*9/10)%i);
            }
            return ans;
        }
    };
    

Log in to reply
 

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