Задача: Взлом замка

Условие: даётся замок, состоящий из четырёх вращающихся дисков, на каждом из которых имеется 10 цифр: от 0 до 9. При этом за раз можно перемещать только одно колесо и на одно значение. 

Изначально замок находится на значении «0000». 

На вход подаётся список блокирующих комбинаций, то есть таких четвёрок цифр, при которых открыть механизм не представляешься возможным. 

Помимо этого даётся шифр открывающий замок, необходимо вычислить наименьшее число перемещений дисков механизма для открытия замка.

Пример:

Ввод: deadends = ["0201","0101","0102","1212","2002"], target = "0202"

Вывод: 6

Объяснение: последовательность, открывающая замок: "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".

Решение задачи на Go:

Сложность:

Временная сложность: O(10^N . N^2 + d)

Пространственная сложность: O(N^2)

Код:

type pair struct {
 current string
 steps   int
}

func openLock(deadends []string, target string) int {
 queue := []pair{}
 seen := make(map[string]bool)

 for _, d := range deadends {
  if d == "0000" {
   return -1
  }
  seen[d] = true
 }
 queue = append(queue, pair{current: "0000", steps: 0})

 for len(queue) > 0 {
  p := queue[0]
  queue = queue[1:]

  if p.current == target {
   return p.steps
  }

  for _, n := range getNeighbors(p.current) {
   if !seen[n] {
    queue = append(queue, pair{current: n, steps: p.steps + 1})
    seen[n] = true
   }
  }
 }
 return -1
}

func getNeighbors(node string) []string {
 neighbors := []string{}
 for i := 0; i < len(node); i++ {
        // first get the number on node[i]
  num := int(node[i] - '0')
  for _, change := range []int{-1, 1} {
            // see if the number can be rorated again
   newNum := (num + change + 10) % 10
            // Add that number back to it's original location
   neighbors = append(neighbors, fmt.Sprintf("%s%d%s", node[0:i], newNum, node[i+1:]))
  }
 }
 return neighbors
}