Open the Lock — BFS State Space

Problem

A lock has 4 circular wheels. From '0000', reach the target avoiding dead-ends. Each turn rotates one wheel one step. Find minimum turns.

Approach — BFS

Each state is a 4-digit string. From each state, generate 8 neighbours (each wheel ±1). BFS gives minimum steps.

Time: O(10^4 * 4) | Space: O(10^4)

Solutions

Python

from collections import deque
class Solution:
    def openLock(self, deadends: list[str], target: str) -> int:
        dead=set(deadends)
        if '0000' in dead: return -1
        if target=='0000': return 0
        visited={'0000'}; q=deque([('0000',0)])
        while q:
            state,turns=q.popleft()
            for i in range(4):
                for d in (1,-1):
                    new=list(state)
                    new[i]=str((int(new[i])+d)%10)
                    ns=''.join(new)
                    if ns==target: return turns+1
                    if ns not in visited and ns not in dead:
                        visited.add(ns); q.append((ns,turns+1))
        return -1

C++

class Solution {
public:
    int openLock(vector<string>& deadends, string target){
        set<string> dead(deadends.begin(),deadends.end());
        if(dead.count("0000")) return -1;
        if(target=="0000") return 0;
        queue<pair<string,int>> q; q.push({"0000",0});
        set<string> vis{"0000"};
        while(!q.empty()){
            auto[state,t]=q.front();q.pop();
            for(int i=0;i<4;i++) for(int d:{1,-1}){
                string ns=state; ns[i]=(ns[i]-'0'+d+10)%10+'0';
                if(ns==target) return t+1;
                if(!vis.count(ns)&&!dead.count(ns)){vis.insert(ns);q.push({ns,t+1});}
            }
        }
        return -1;
    }
};

Complexity

Time: O(10^4) | Space: O(10^4)