题解67 | 其实门没锁，是你的心锁了#开锁#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param vec string字符串vector
     * @param tar string字符串
     * @return int整型
     */
    string M(string s, int j) {
        if (s[j] == '9') s[j] = '0';
        else s[j] = (int)s[j] + 1;
        return s;
    }
    string m(string s, int j) {
        if (s[j] == '0') s[j] = '9';
        else s[j] = (int)s[j] - 1;
        return s;
    }
    int open(vector<string>& vec, string tar) {
        // write code here gracefully
        int n = tar.length();
        int step = 0;
        unordered_set<string> a, b;
        unordered_set<string> v;

        for (auto dead : vec) v.insert(dead);
        
        a.insert("0000");
        b.insert(tar);

        while (!a.empty() && !b.empty()) {
            unordered_set<string> t;

            for (string i : a) {

                if (v.count(i)) continue;
                if (b.count(i)) return step;
                
                v.insert(i);

                for (int j = 0; j < n; j++) {
                    string H = M(i, j);
                    if (!v.count(H)) t.insert(H);
                    string h = m(i, j);
                    if (!v.count(h)) t.insert(h);
                }

            }
            a = b;
            b = t;
            step++;
        }
        return -1;

    }
};

基本算法思想:

1. 使用双向BFS（双向广度优先搜索）来搜索从"0000"到目标字符串的最短路径。

2. 使用两个集合a和b来分别存储当前步数能达到的状态，然后交替更新a和b直到找到目标字符串或者两个集合都为空。

时间复杂度：

O(N^2) ，N为目标字符串的长度，每个状态可以扩展出N个新的状态，最坏情况下需要扩展N次。

空间复杂度：

O(N) ，使用了两个集合a和b来存储状态，以及一个集合v来存储已经访问过的状态，最坏情况下空间复杂度为O(N)。