752. Open the Lock #

Problem #

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: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and 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.

Example 1:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation:
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".

Example 2:

Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation:
We can turn the last wheel in reverse to move from "0000" -> "0009".

Example 3:

Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation:
We can't reach the target without getting stuck.

Example 4:

Input: deadends = ["0000"], target = "8888"
Output: -1

Constraints:

1 <= deadends.length <= 500
deadends[i].length == 4
target.length == 4
target will not be in the list deadends.
target and deadends[i] consist of digits only.

Problem Summary #

You have a combination lock with four circular wheels. Each wheel has 10 digits: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’. Each wheel can rotate freely: for example, ‘9’ can become ‘0’, and ‘0’ can become ‘9’. Each rotation can only rotate one wheel by one digit. The initial number of the lock is ‘0000’, a string representing the digits of the four wheels. The list deadends contains a set of dead-end numbers; once the digits on the wheels match any element in the list, the lock will be permanently locked and can no longer be rotated. The string target represents the number that can unlock the lock. You need to return the minimum number of rotations required to unlock it; if it cannot be unlocked no matter what, return -1.

Solution Approach #

This problem can be transformed into finding the shortest path from the starting point to the endpoint. Use breadth-first search. In each BFS step, enumerate the states after rotating one digit once, and use visited to record whether a state has been searched. If it has not been searched, add it to the queue and continue searching in the next round. If target is found, return the corresponding number of rotations. If the search completes and target is still not found, it means the lock cannot be opened, so return -1. Special case: if target is the initial number 0000, directly return the answer 0.
Before BFS, first put deadends into a map, and during the search check whether a deadend has been reached. If the initial number 0000 appears in deadends, directly return the answer -1.

Code #

package leetcode

func openLock(deadends []string, target string) int {
	if target == "0000" {
		return 0
	}
	targetNum, visited := strToInt(target), make([]bool, 10000)
	visited[0] = true
	for _, deadend := range deadends {
		num := strToInt(deadend)
		if num == 0 {
			return -1
		}
		visited[num] = true
	}
	depth, curDepth, nextDepth := 0, []int16{0}, make([]int16, 0)
	var nextNum int16
	for len(curDepth) > 0 {
		nextDepth = nextDepth[0:0]
		for _, curNum := range curDepth {
			for incrementer := int16(1000); incrementer > 0; incrementer /= 10 {
				digit := (curNum / incrementer) % 10
				if digit == 9 {
					nextNum = curNum - 9*incrementer
				} else {
					nextNum = curNum + incrementer
				}
				if nextNum == targetNum {
					return depth + 1
				}
				if !visited[nextNum] {
					visited[nextNum] = true
					nextDepth = append(nextDepth, nextNum)
				}
				if digit == 0 {
					nextNum = curNum + 9*incrementer
				} else {
					nextNum = curNum - incrementer
				}
				if nextNum == targetNum {
					return depth + 1
				}
				if !visited[nextNum] {
					visited[nextNum] = true
					nextDepth = append(nextDepth, nextNum)
				}
			}
		}
		curDepth, nextDepth = nextDepth, curDepth
		depth++
	}
	return -1
}

func strToInt(str string) int16 {
	return int16(str[0]-'0')*1000 + int16(str[1]-'0')*100 + int16(str[2]-'0')*10 + int16(str[3]-'0')
}