Open the Lock
Medium · Queue & Deque · about 25 minutes
Asked at Google, Amazon, Uber.
A combination lock has four dials, each showing a digit from 0 to 9, and starts at "0000". A move turns one dial by one step in either direction (9 and 0 are neighbors). Codes listed in deadends freeze the lock, so you must never pass through them. Find the fewest moves to reach target, or return -1 if it can't be reached.