752.md

【中规中矩】752. 打开转盘锁（宽度优先搜索）

解题思路

可以这样思考，先不考虑deadends这么做？之后做出来再考虑如果加上这个限制怎么办？ Step 1： 不考虑deadends相对简单，只要对每一位数字尝试加一减一穷举八种情况，然后在BF层层搜索直到找到目标值就可以了。 Step 2：考虑deadends的话，其实只是多一个check当前搜索到的值是不是在set里面就好了，是的话就跳过。

代码

不考虑deadends的解法

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> deads(deadends.begin(), deadends.end());
        unordered_set<string> visited;
        queue<string> q;

        int steps = 0;
        q.push("0000");
        visited.insert("0000");
        while (!q.empty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                auto cur = q.front();
                q.pop();
                
                if (deads.count(cur)) {
                    continue; // skip dead codes
                }
                if (cur == target) {
                    return steps;
                }

                for (int j = 0; j < 4; j++) {
                    auto up = plusOne(cur, j);
                    if (!visited.count(up)) {
                        q.push(up);
                        visited.insert(up);
                    }    
                    auto down = minusOne(cur, j);
                    if (!visited.count(down)) {
                        q.push(down);
                        visited.insert(down);
                    }    
                }
            }
            steps++;
        }
        
        return -1;
    }

private:
    string plusOne(string cur, int j) {
        auto res = cur;
        res[j] = ((res[j] - '0' + 1) % 10) + '0';
        return res;
    }

    string minusOne(string cur, int j) {
        auto res = cur;
        res[j] = ((res[j] - '0' - 1 + 10) % 10) + '0';
        return res;
    }
};

考虑deadends的解法，只是多一个check当前搜索到的值是不是在set里面就好了，是的话就跳过。

// With deadends
class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        queue<string> q{{"0000"}};
        unordered_set<string> visited;
        unordered_set<string> deads(deadends.begin(), deadends.end());

        int steps = 0;
        while (!q.empty()) {
            int size = q.size();
            while (size--) {
                auto cur = q.front(); q.pop();
                if (cur == target) {
                    return steps;
                }

                if (deads.count(cur) || visited.count(cur)) { //只多了前半部分的check deadends
                    continue;
                }
                visited.insert(cur);

                for (int i = 0; i < 4; i++) {
                    q.push(plusOne(cur, i));
                    q.push(minusOne(cur, i));
                }
            }
            steps++;
        }

        return -1;
    }

private:
    string plusOne(string cur, int j) {
        auto res = cur;
        res[j] = ((res[j] - '0' + 1) % 10) + '0';
        return res;
    }

    string minusOne(string cur, int j) {
        auto res = cur;
        res[j] = ((res[j] - '0' - 1 + 10) % 10) + '0';
        return res;
    }
};

// Implementation 2 using lambda helper func
class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        queue<string> q{{"0000"}};
        int steps = 0;
        unordered_set<string> deadSet(deadends.begin(), deadends.end());
        unordered_set<string> visited;
        while (!q.empty()) {
            for (int k = q.size(); k > 0; k--) {
                auto cur = q.front(); q.pop();
                if(deadSet.count(cur)) {
                    continue;
                }

                if (cur == target) {
                    return steps;
                }
                for (int i = 0; i < cur.size(); i++) {
                    auto nextPwd = [&](bool isUp) {
                        auto next = cur;
                        int offset = isUp ? 1 : -1;
                        next[i] = ((next[i] - '0' + offset + 10) % 10 + '0');
                        if (!visited.count(next)) {
                            visited.insert(next);
                            q.push(next);
                        }
                        return next;
                    };
                    auto nextUp = nextPwd(true);
                    auto nextDown = nextPwd(false);
                }
            }
            steps++;
        }

        return -1;
    }
};

class Solution(object):
    def openLock(self, deadends, target):
        def neighbors(node):
            for i in xrange(4):
                x = int(node[i])
                for d in (-1, 1):
                    y = (x + d) % 10
                    yield node[:i] + str(y) + node[i + 1:]

        dead = set(deadends)
        queue = collections.deque([('0000', 0)])
        seen = {'0000'}

        while queue:
            node, depth = queue.popleft()
            if node == target:
                return depth
            elif node in dead:
                continue
            for neighbor in neighbors(node):
                if neighbor not in seen:
                    seen.add(neighbor)
                    queue.append((neighbor, depth + 1))
        return -1

点我赞赏作者

github 题解