Open the Lock Problem – BFS Solution in Java

You have a lock with four circular wheels, each showing a digit from '0' to '9'. Starting from the initial state "0000", you must reach a target combination without ever entering any of the forbidden dead‑end states. Each move rotates a single wheel one step forward or backward.

Examples: Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202" → Output: 6 (one possible sequence is "0000" → "1000" → "1100" → "1200" → "1201" → "1202" → "0202"). Input: deadends = ["8888"], target = "0009" → Output: 1 (rotate the last wheel backward). Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888" → Output: -1 (target is unreachable). Input: deadends = ["0000"], target = "8888" → Output: -1 (starting state is a dead‑end).

The problem can be modeled as a graph where each node is a 4‑digit string and edges connect nodes that differ by one wheel rotation. A breadth‑first search (BFS) from the start node explores the graph level by level, guaranteeing the shortest path to the target.

Below is a generic BFS traversal for a binary tree (illustrative only): public void levelOrder(TreeNode tree) { Queue queue = new LinkedList<>(); queue.add(tree); int level = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); System.out.println(node.val); if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } level++; System.out.println(level); } }

The actual solution for the lock problem in Java is as follows: public int openLock(String[] deadends, String target) { Set set = new HashSet<>(Arrays.asList(deadends)); String startStr = "0000"; if (set.contains(startStr)) return -1; Queue queue = new LinkedList<>(); Set visited = new HashSet<>(); queue.offer(startStr); visited.add(startStr); int level = 0; while (!queue.isEmpty()) { int size = queue.size(); while (size-- > 0) { String str = queue.poll(); for (int i = 0; i < 4; i++) { char ch = str.charAt(i); String strAdd = str.substring(0, i) + (ch == '9' ? 0 : ch - '0' + 1) + str.substring(i + 1); String strSub = str.substring(0, i) + (ch == '0' ? 9 : ch - '0' - 1) + str.substring(i + 1); if (strAdd.equals(target) || strSub.equals(target)) return level + 1; if (!visited.contains(strAdd) && !set.contains(strAdd)) { queue.offer(strAdd); visited.add(strAdd); } if (!visited.contains(strSub) && !set.contains(strSub)) { queue.offer(strSub); visited.add(strSub); } } } level++; } return -1; }

This implementation expands each node into up to eight neighboring states (adding or subtracting one from each wheel), skips already visited or dead‑end states, and returns the depth at which the target is first encountered, which corresponds to the minimum number of moves.