We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Open the Lock

Difficulty: Medium

Problem Description

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. The lock initially starts at '0000'. You are given a list of deadends, meaning if the lock displays any of these codes, 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.

Key Insights

  • The lock can be represented as a 4-digit string where each digit can be incremented or decremented.
  • A breadth-first search (BFS) is suitable for finding the shortest path in an unweighted graph (or in this case, the minimum moves to the target).
  • Each state of the lock can lead to up to 8 new states (by turning each wheel up and down).
  • Deadends must be avoided as they are non-traversable states.

Space and Time Complexity

Time Complexity: O(10^4) - Each of the 10,000 possible states can be visited at most once during the BFS. Space Complexity: O(10^4) - The space used by the queue and the set to track visited states.

Solution

The solution employs a breadth-first search (BFS) strategy. We start from the initial state '0000' and explore all possible moves. Each move can be made by turning any of the four wheels up or down. We maintain a queue to explore each state and a set to track visited states, including the deadends. If we reach the target state, we return the number of moves taken. If the BFS completes and we haven't reached the target, we return -1.

Code Solutions

from collections import deque

def openLock(deadends, target):
    dead_set = set(deadends)
    if '0000' in dead_set:
        return -1
        
    queue = deque(['0000'])
    visited = set(['0000'])
    steps = 0
    
    while queue:
        for _ in range(len(queue)):
            current = queue.popleft()
            if current == target:
                return steps
            
            for i in range(4):
                for d in [-1, 1]:
                    next_digit = (int(current[i]) + d) % 10
                    next_lock = current[:i] + str(next_digit) + current[i + 1:]
                    if next_lock not in visited and next_lock not in dead_set:
                        visited.add(next_lock)
                        queue.append(next_lock)
        steps += 1
        
    return -1
← Back to All Questions