Сложность: medium
Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.
После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.
Пример:
Input: n = 1, k = 2
Output: "10"
👨💻 Алгоритм:
1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].
2⃣Используйте алгоритм Эйлерова пути или цикла для нахождения пути, который проходит через каждое ребро ровно один раз.
3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.
😎 Решение:
func crackSafe(_ n: Int, _ k: Int) -> String {
var seen = Set<String>()
var result = [Character]()
func dfs(_ node: String) {
for x in 0..<k {
let neighbor = node + String(x)
if !seen.contains(neighbor) {
seen.insert(neighbor)
dfs(String(neighbor.dropFirst()))
result.append(Character(String(x)))
}
}
}
let startNode = String(repeating: "0", count: n - 1)
dfs(startNode)
return startNode + String(result)
}Ставь 👍 и забирай 📚 Базу знаний