752. Open the Lock

---

My Solution

The Key Idea for Solving This Coding Question

C++ Code

class Solution {
public:
    int openLock(vector<string> &deadends, string target) {
        unordered_set<string> deadendSet(deadends.begin(), deadends.end());
        if (deadendSet.find("0000") != deadendSet.end()) {
            return -1;
        }

        unordered_set<string> visited;
        queue<string> q;
        int minTurns = 0;

        q.push("0000");
        visited.insert("0000");
        while (!q.empty()) {
            int qLen = q.size();
            for (int i = 0; i < qLen; ++i) {
                string guess = q.front();
                q.pop();

                if (guess == target) {
                    return minTurns;
                }

                for (int j = 0; j < guess.size(); ++j) {
                    string up = turnUp(guess, j);
                    if (deadendSet.find(up) == deadendSet.end() && 
                        visited.find(up) == visited.end()) {
                        q.push(up);
                        visited.insert(up);
                    }

                    string down = turnDown(guess, j);
                    if (deadendSet.find(down) == deadendSet.end() && 
                        visited.find(down) == visited.end()) {
                        q.push(down);
                        visited.insert(down);
                    }
                }
            }
            ++minTurns;
        }

        return -1;
    }

private:
    string turnUp(string guess, int j) {
        if (guess[j] == '9') {
            guess[j] = '0';
        } else {
            ++guess[j];
        }
        return guess;
    }

    string turnDown(string guess, int j) {
        if (guess[j] == '0') {
            guess[j] = '9';
        } else {
            --guess[j];
        }
        return guess;
    }
};

Time Complexity

Space Complexity

Miscellane