Задача: 753. Cracking the Safe Сложность: 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⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры. 😎 Решение: using System.Collections.Generic; using System.Text; public class Solution { public string CrackSafe(int n, int k) { var seen = new HashSet<string>(); var result = new StringBuilder(); string startNode = new string('0', n - 1); Dfs(startNode, k, seen, result); result.Append(startNode); return result.ToString(); } private void Dfs(string node, int k, HashSet<string> seen, StringBuilder result) { for (int x = 0; x < k; x++) { string neighbor = node + x; if (!seen.Contains(neighbor)) { seen.Add(neighbor); Dfs(neighbor.Substring(1), k, seen, result); result.Append(x); } } } } Ставь 👍 и забирай 📚 Базу знаний