SeniorCodeRareNot answered yet
Restore all valid IPv4 addresses from a digit string
Given a string of digits, return every valid IPv4 address that yields the string when its dots are removed. An address is four octets, each 1–3 digits, value 0–255, with no leading zeros except the single digit "0".
Requirements:
- Backtracking over the four octet splits.
std::vector<std::string> restoreIp(const std::string& s) {
// your code here
}Write the implementation.
Backtrack: place three dots splitting the string into four octets. At each step try a 1-, 2-, or 3-digit octet, accepting it only if its value is 0–255 with no leading zero (unless exactly "0"). When all four octets consume the whole string, record the address.
- ✗Allowing leading zeros like
01or00in an octet - ✗Accepting octet values above 255
- ✗Not requiring all four octets to consume the entire string
- →Which inputs produce zero valid addresses?
- →How would you extend this to IPv6 grouping?
Contents
Task
Restore all valid IPv4 addresses from a digit string by backtracking.
Solution
static bool validOctet(const std::string& o) {
if (o.empty() || o.size() > 3) return false;
if (o.size() > 1 && o[0] == '0') return false; // leading zero
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);
}
}Key points
- Backtrack over four octets, each 1–3 digits long.
- Each octet is 0–255 with no leading zero (except
"0"). - All four octets must consume the whole string.
Contents
