Объясняем условие «на пальцах»
🌐 Что такое IP-адрес?
Представь, что IP-адрес — это почтовый индекс для компьютера. Он выглядит так:
192.168.1.1
↑ ↑ ↑ ↑
4 числа, разделённые точками
Правила валидного IP-адреса:
Суть задачи:
Тебе дали строку из цифр (например, "25525511135").
Нужно расставить 3 точки так, чтобы получилась все возможные валидные IP-адреса.
⚠️ Важно: Нельзя менять порядок цифр или удалять их! Только вставлять точки.
🎮 Примеры «на пальцах»
Пример 1: s = "25525511135"
Возможные варианты:
✅ "255.255.11.135" → все части валидны
✅ "255.255.111.35" → тоже валидно
❌ "25.52.55.11135" → 11135 > 255, нельзя!
❌ "2.5.5.25511135" → последняя часть слишком длинная
Ответ: ["255.255.11.135", "255.255.111.35"]
Пример 2: s = "0000"
Единственный вариант:
✅ "0.0.0.0" → все части = 0, это разрешено!
Ответ: ["0.0.0.0"]
Пример 3: s = "101023"
Пример 3: s = "101023"
Возможные варианты:
✅ "1.0.10.23"
✅ "1.0.102.3"
✅ "10.1.0.23"
✅ "10.10.2.3"
✅ "101.0.2.3"
Ответ: 5 адресов
Как думать, как программист?
Ключевая идея: Бэктрекинг (перебор с возвратом)
Представь, что ты ставишь точки по очереди:
Строка: "101023"
↑
Ставим первую точку после 1, 2 или 3 цифр:
Вариант 1: "1|01023" → первая часть = "1" ✅
Вариант 2: "10|1023" → первая часть = "10" ✅
Вариант 3: "101|023" → первая часть = "101" ✅
Для каждого варианта повторяем то же самое для второй, третьей и четвёртой части...
Алгоритм шаг за шагом:
- База рекурсии: если поставили 4 точки И использовали все цифры → нашли адрес! ✅
- Пробуем взять 1, 2 или 3 цифры для текущей части
- Проверяем валидность:Нет ли ведущих нулей? ("01" ❌, "0" ✅)
Число ≤ 255? - Рекурсивно идём дальше с оставшейся строкой
- Если не подошло — «откатываемся» (бэктрекинг) и пробуем другой вариант
Решение на Java (бэктрекинг)
Заключение
Пример, рассмотренный в статье, можно найти по адресу:
https://github.com/ShkrylAndrei/leetcode/blob/main/src/main/java/info/shkryl/task93_restoreIpAddresses/Solution.java