LeetCode GO-752. Open the turntable lock

This is the 24th day of my participation in the Gwen Challenge.More article challenges

For a better tomorrow, keep brushing LeetCode!

The title

You have a turntable lock with four round paddles. Each dial wheel has 10 Numbers: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’. Each dial wheel can rotate freely: for example, ‘9’ becomes ‘0’ and ‘0’ becomes ‘9’. Each rotation can only rotate one digit of one dial wheel.

The initial lock number is ‘0000’, a string representing the numbers of the four dial wheels.

The list deadends contains a set of death numbers. Once the number of the dial wheel matches any element in the list, the lock is permanently locked and cannot be rotated.

The string target represents the number that can be unlocked. You need to give the minimum number of rotations required to unlock it. If you can’t unlock it anyway, return -1.

Example 1:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202" Could move the sequence of "0000" - > "1000" - > "1100" - > "1200" - > "1201" - > "1202" - > "0202". Note that sequences such as "0000" -> "0001" -> "0002" -> "0102" -> "0202" cannot be unlocked because the lock will be locked when "0102" is tapped.Copy the code

Example 2:

Deadends = ["8888"], target = "0009" Output: 1Copy the code

Example 3:

Input: Deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888" Output: -1 Description: Cannot rotate to target number and is not locked.Copy the code

Example 4:

Input: Deadends = ["0000"], target = "8888" Text 1 <= deadends. Length <= 500 deadends[I]. Length == 4 target Deadends [I] consists of only a number of digitsCopy the code

Solution one – BFS

Their thinking

Using a queue for breadth-first search, let the number currently searched be status and the number of rotations be step. We can enumerate the number of rotations obtained by status in one rotation. Let one of these numbers be next_status, and if it has not been searched, we queue (next_status,step+1). If target is found, we return its corresponding rotation number step and use a hash table to store the searched state. If target is not found, -1 is returned.

code

func openLock(deadends []string, target string) int {
    const start = "0000"
    if target == start {
        return 0
    }

    dead := map[string]bool{}
    for _, s := range deadends {
        dead[s] = true
    }
    if dead[start] {
        return - 1
    }

    // enumeration status The number obtained by a rotation
    get := func(status string) (ret []string) {
        s := []byte(status)
        for i, b := range s {
            s[i] = b - 1
            if s[i] < '0' {
                s[i] = '9'
            }
            ret = append(ret, string(s))
            s[i] = b + 1
            if s[i] > '9' {
                s[i] = '0'
            }
            ret = append(ret, string(s))
            s[i] = b
        }
        return
    }

    type pair struct {
        status string
        step   int
    }
    q := []pair{{start, 0}}
    seen := map[string]bool{start: true}
    for len(q) > 0 {
        p := q[0]
        q = q[1:]
        for _, nxt := range get(p.status) {
            if! seen[nxt] && ! dead[nxt] {if nxt == target {
                    return p.step + 1
                }
                seen[nxt] = true
                q = append(q, pair{nxt, p.step + 1})}}}return - 1
}
Copy the code

Topic link

Open the turntable lock