Show problems as
Classic problem #752MediumArrayHash TableStringBreadth-First SearchBidirectional Search

Open the Lock

Real-world version: Four-Drum Seal Dial
Tracked in this browser only
Read Open the Lock on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A freight container is closed with a numeric seal built from four drums standing side by side, each showing one digit from 0 to 9. A reading of the seal is written as a four-character string of digits, leftmost drum first.

Turning one drum one notch, in either direction, counts as one move. A drum showing 9 turned upward comes round to 0, and a drum showing 0 turned downward comes round to 9. Only one drum moves at a time.

Certain readings seize the mechanism: the moment the seal shows a reading listed in jammed, the drums lock for good. A reading in jammed therefore cannot be shown at any point, not even in passing on the way somewhere else.

A fresh seal reads 0000. Return the fewest moves needed to bring the seal to target, or -1 if target cannot be shown at all. target is never listed in jammed, and jammed may list the same reading more than once.

Examples

Example 1

Input
jammed = ["0810", "0090"], target = "0091"
Output
2

Turning the last drum up once shows 0001, then turning the third drum down once brings it round to 9 and shows 0091. Neither reading is listed in jammed.

Example 2

Input
jammed = ["0001"], target = "0002"
Output
4

The seal can show 1000, then 1001, then 1002, then 0002, four moves in all, and none of those four readings is listed in jammed.

Example 3

Input
jammed = ["0000"], target = "0210"
Output
-1

The fresh seal already shows a jammed reading, so the drums are locked before any move is made.

Constraints

  • 1 <= jammed.length <= 500
  • jammed[i].length == 4
  • target.length == 4
  • target and every jammed[i] consist of digits only
  • target does not appear in jammed

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def fewest_seal_moves(jammed: list[str], target: str) -> int:
Java
public int fewestSealMoves(String[] jammed, String target)

More on the same topics