You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

&nbsp;
Example 1:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation: 
A sequence of valid moves would be "0000" -&gt; "1000" -&gt; "1100" -&gt; "1200" -&gt; "1201" -&gt; "1202" -&gt; "0202".
Note that a sequence like "0000" -&gt; "0001" -&gt; "0002" -&gt; "0102" -&gt; "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".


Example 2:

Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation: We can turn the last wheel in reverse to move from "0000" -&gt; "0009".


Example 3:

Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation: We cannot reach the target without getting stuck.


&nbsp;
Constraints:


	1 &lt;= deadends.length &lt;= 500
	deadends[i].length == 4
	target.length == 4
	target will not be in the list deadends.
	target and deadends[i] consist of digits only.


class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        def neighbor(s):
            res = []
            for i, c in enumerate(s):
                res.append(s[:i] + chr((ord(c) - ord('0') + 9) % 10 + ord('0')) + s[i + 1:])
                res.append(s[:i] + chr((ord(c) - ord('0') + 1) % 10 + ord('0')) + s[i + 1:])
            return res
        
        deadends = set(deadends)
        if "0000" in deadends:
            return -1
        ans = 0
        queue = deque(["0000"])
        vis = set()
        while queue:
            l = len(queue)
            for _ in range(l):
                cur = queue.popleft()
                if cur == target:
                    return ans
                for nxt in neighbor(cur):
                    if nxt not in vis and nxt not in deadends:
                        queue.append(nxt)
                        vis.add(nxt)
            ans += 1
        return -1
class Solution {
    public int openLock(String[] deadends, String target) {
// Converted target to Integer type.
        int t = Integer.parseInt(target);
        HashSet<Integer> visited = new HashSet<>();

// Converting deadend strings to Integer type. To prevent from visiting deadend, we already mark them visited.
        for(String str: deadends){
            visited.add(Integer.parseInt(str));
        }
// BFS
        Queue<Integer> q = new ArrayDeque<>();
// We make sure that 0 itself isn't a deadend
        if(visited.contains(0)){
            return -1;
        }
        q.add(0);
        visited.add(0);
        int level = 0;
        while(q.size() > 0){
            int size = q.size();
            while(size-->0){
                int elem = q.remove();
                if(t == elem){
                    return level;
                }
// Will help check 4 digits of the element. From digit with low precendence(ones place) to high precedence(thousands place)
                for(int i = 1; i < 10000; i= i*10){
// The wheel can be rotated in two directions. Hence two numbers.
                    int num1;
                    int num2;
// The wheel at 0 can become 1 or 9 due to wrapping.
                    if(elem / i % 10 == 0){
                        num1=elem + i;
                        num2 = elem+ i * 9;
                    }
// The wheel at 9 can become 0 or 8 due to wrapping.
                    else if(elem / i % 10 == 9){
                        num1 = elem - i * 9;
                        num2 = elem -i;
                    }
                    else{
                        num1 = elem -i;
                        num2 = elem + i;
                    }
// Checking if numbers have already been visited.
                    if(!(visited.contains(num1))){
                            visited.add(num1);
                            q.add(num1);
                        }
                    if(!(visited.contains(num2))){
                        visited.add(num2);
                        q.add(num2);
                    }
                }
            }
            level++;
        }
        return -1;
    }
}
class Solution {
public:
    void setPermutations(const string& s, queue<pair<string, int>>& q, int count) {
        for (int i=0; i<4; i++) {
            int j = s[i]-'0';
            char b = (10+j-1)%10 + '0', n = (10+j+1)%10 + '0';
            auto tmp = s; tmp[i]=b;
            q.push({tmp, count+1});
            tmp = s; tmp[i]=n;
            q.push({tmp, count+1});
        }
    }
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> deadies(deadends.begin(), deadends.end());
        queue<pair<string, int>> q({{"0000", 0}});
        while (!q.empty()) {
            auto t = q.front();
            q.pop();
            if (deadies.count(t.first))
                continue;
            if (t.first==target)
                return t.second;
            deadies.insert(t.first);
            setPermutations(t.first, q, t.second);
        }
        return -1;
    }
};
var openLock = function(deadends, target) {
    if(deadends.includes('0000')) {
        return -1
    }
    // treat deadends like visited
    // if a number is in visited/deadends, simply ignore it
    const visited = new Set(deadends)
    
    
    const queue = [['0000', 0]];
    visited.add('0000')

    while(queue.length) {
        const [cur, count] = queue.shift()
        if(cur === target) {
            return count
        }
        
        // each number will create 8 more different paths to check
        
        // e.g. if cur = 0000. 8 next/prev numbers to check are
        // 1000, 9000, 0100, 0900, 0010, 0090, 0001, 0009
        for(let i=0; i<4; i++) {
            const c = cur[i]
           
            let up = Number(c) + 1;
            let down = Number(c) - 1;
            // if up is 9, then up + 1 = 10 -> set it  to 0
            if(up === 10) {
                up = '0';
            }
            // if down is 0. then down - 1 = -1 -> set to 9
            if(down === -1) {
                down = '9'
            }
            
            const next =  cur.substring(0, i) + up  + cur.substring(i+1)
            const prev =  cur.substring(0, i) + down + cur.substring(i + 1)
            
            // if not visited, push to queue
            if(!visited.has(next)) {
                visited.add(next)
                queue.push([next, count + 1])   
            }

            if(!visited.has(prev)) {
                visited.add(prev)
                queue.push([prev, count + 1])   
            }
        }
    }
    
    return -1;
};
Open the Lock