752. Open the Lock

Time: O(10^4)

Space: O(10^4)

Intuition

BFS on the state space of 4-digit combinations. Each state has 8 neighbors (turn each of 4 wheels ±1). Find shortest path from "0000" to target.

Algorithm

1Add deadends to visited set.
2BFS from "0000": generate 8 neighbors (wheel±1 mod 10).
3Skip visited and deadends.
4Return steps when target is reached.

Example Walkthrough

Input: deadends=["0201","0101","0102","1212","2002"], target="0202"

1.BFS explores states, avoiding deadends, finds shortest path.

Output: 6

Common Pitfalls

•If "0000" is in deadends, return -1 immediately. Use bidirectional BFS for speed.

752.cs

// Approach: BFS from "0000"; each state has 8 neighbors (4 wheels × 2 directions); skip dead-end states.
// Time: O(10^4) Space: O(10^4)

public class Solution
{
    public int OpenLock(string[] deadends, string target)
    {
        HashSet<string> set = new HashSet<string>();

        foreach (string val in deadends)
            set.Add(val);

        if (set.Contains("0000"))
            return -1;

        if (target.Equals("0000"))
            return 0;

        int ans = 0;
        Queue<string> q = new Queue<string>();
        q.Enqueue("0000");

        while (q.Count > 0)
        {
            ans++;
            for (int sz = q.Count; sz > 0; sz--)
            {
                char[] str = q.Dequeue().ToCharArray();

                for (int i = 0; i < 4; i++)
                {
                    char cache = str[i];
                    str[i] = (str[i] == '9' ? '0' : (char)(str[i] + 1));
                    string word = new string(str);
                    if (word == target)
                        return ans;

                    if (!set.Contains(word))
                    {
                        q.Enqueue(word);
                        set.Add(word);
                    }

                    str[i] = cache;

                    str[i] = (str[i] == '0' ? '9' : (char)(str[i] - 1));
                    word = new string(str);
                    if (word == target)
                        return ans;

                    if (!set.Contains(word))
                    {
                        q.Enqueue(word);
                        set.Add(word);
                    }

                    str[i] = cache;
                }
            }
        }

        return -1;
    }
}

Was this solution helpful?