SeniorКодРедкоЕщё не отвечали
Восстановить все валидные IPv4-адреса из строки цифр
Дана строка цифр. Верните каждый валидный IPv4-адрес, дающий эту строку при удалении точек. Адрес — четыре октета, каждый 1–3 цифры, значение 0–255, без ведущих нулей кроме одиночного "0".
Требования:
- Бэктрекинг по четырём разбиениям на октеты.
std::vector<std::string> restoreIp(const std::string& s) {
// ваш код здесь
}Допишите реализацию.
Бэктрекинг: расставьте три точки, разбивая строку на четыре октета. На шаге пробуйте октет из 1, 2 или 3 цифр, принимая его лишь если значение 0–255 без ведущего нуля (кроме ровно "0"). Когда все четыре октета покрывают всю строку, запишите адрес.
- ✗Разрешать ведущие нули вроде
01или00в октете - ✗Принимать значения октетов больше 255
- ✗Не требовать, чтобы все четыре октета покрывали всю строку
- →Какие входы дают ноль валидных адресов?
- →Как расширить это на группировку IPv6?
Оглавление
Задача
Восстановите все валидные IPv4-адреса из строки цифр бэктрекингом.
Решение
#include <vector>
#include <string>
static bool validOctet(const std::string& o) {
if (o.empty() || o.size() > 3) return false;
if (o.size() > 1 && o[0] == '0') return false; // ведущий ноль
return std::stoi(o) <= 255;
}
static void bt(const std::string& s, int pos, int part,
std::string cur, std::vector<std::string>& out) {
if (part == 4) { if (pos == (int)s.size()) out.push_back(cur); return; }
for (int len = 1; len <= 3 && pos + len <= (int)s.size(); ++len) {
std::string oct = s.substr(pos, len);
if (!validOctet(oct)) continue;
bt(s, pos + len, part + 1,
cur.empty() ? oct : cur + "." + oct, out);
}
}
std::vector<std::string> restoreIp(const std::string& s) {
std::vector<std::string> out;
bt(s, 0, 0, "", out);
return out;
}Ключевые моменты
- Бэктрекинг по четырём октетам, длина 1–3 цифры.
- Каждый октет 0–255, без ведущего нуля (кроме
"0"). - Все четыре октета должны покрыть всю строку.
Оглавление
