Сложность: 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⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.
😎 Решение:
def crackSafe(n, k):
seen = set()
result = []
def dfs(node):
for x in range(k):
neighbor = node + str(x)
if neighbor not in seen:
seen.add(neighbor)
dfs(neighbor[1:])
result.append(str(x))
start_node = '0' * (n - 1)
dfs(start_node)
return start_node + ''.join(result)
Ставь 👍 и забирай 📚 Базу знаний