Validate and restore IPv4 addresses
Company: Flexport
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Design and implement the following IPv4 tasks.
a) Validate dotted IPv4: Write a function isValidIPv4
(s) that returns true if s is a valid dotted-decimal IPv4 address and false otherwise.
Requirements:
- Exactly four decimal octets separated by three dots.
- Each octet is digits only and represents an integer in [0, 255].
- No leading zeros unless the octet is exactly "0".
- No plus/minus signs, whitespace, or extra characters.
Examples: "255.255.11.135" -> true; "-1.255.11.135" -> false; "01.2.3.4" -> false; "256.0.0.1" -> false.
b) Validate undelimited IPv4 possibility: Given a string s consisting only of digits (no dots), return true if it can be segmented into a valid IPv4 by inserting three dots under the same rules as
(a); otherwise return false.
Examples: "25525511135" -> true (e.g., 255.255.11.
135); "0002555" -> true (e.g., 0.0.255.
55); "123" -> false.
c) Restore all valid IPv4 addresses: Given a string s of digits, return all valid IPv4 addresses formed by inserting three dots under the rules above. Return in any order without duplicates.
Example: "25525511135" -> ["255.255.11.135", "255.255.111.35"].
Constraints for
(b) and
(c): 1 <= s.length <= 12. Aim for an efficient solution (typical approach uses DFS/backtracking).
Quick Answer: This question evaluates string processing, strict input validation rules, and constrained combinatorial search skills (e.g., backtracking) for generating and verifying IPv4 addresses.
Validate Dotted-Decimal IPv4 Address
Write a function `isValidIPv4(s)` that returns `true` if `s` is a valid dotted-decimal IPv4 address and `false` otherwise.
A string is a valid IPv4 address when ALL of the following hold:
- It has exactly four decimal octets separated by exactly three dots.
- Each octet contains digits only and represents an integer in the range [0, 255].
- An octet has no leading zeros unless it is exactly "0" (so "0" is valid but "00" and "01" are not).
- There are no plus/minus signs, no whitespace, and no extra characters anywhere in the string.
Examples:
- "255.255.11.135" -> true
- "-1.255.11.135" -> false (minus sign)
- "01.2.3.4" -> false (leading zero)
- "256.0.0.1" -> false (octet out of range)
Constraints
- The input is an arbitrary string; it may contain non-digit characters, signs, or whitespace.
- A valid address has exactly four octets and exactly three dots.
- Each octet is in [0, 255] with no leading zeros (except the single character "0").
- Empty octets (e.g. "1..2.3") and missing/extra dots are invalid.
Examples
Input: ("255.255.11.135",)
Expected Output: True
Explanation: All four octets are in range with no leading zeros.
Input: ("-1.255.11.135",)
Expected Output: False
Explanation: The first octet contains a minus sign, which is not allowed.
Hints
- Split on '.' and immediately reject if you do not get exactly four parts.
- Use a digits-only check (e.g. str.isdigit()) to rule out signs, spaces, and empty octets in one shot.
- Reject any multi-character octet whose first character is '0' to enforce the no-leading-zero rule, then compare the integer value against 255.
Can a Digit String Be Segmented into a Valid IPv4?
Given a string `s` consisting only of digits (no dots), return `true` if it can be segmented into a valid IPv4 address by inserting exactly three dots, using the same rules as a standard dotted-decimal IPv4 address; otherwise return `false`.
Rules for each resulting octet:
- Contains digits only and represents an integer in [0, 255].
- No leading zeros unless the octet is exactly "0".
You must use every character of `s` and produce exactly four octets.
Examples:
- "25525511135" -> true (e.g., 255.255.11.135)
- "0025555" -> true (e.g., 0.0.255.55)
- "123" -> false (cannot be split into four non-empty octets)
Constraint: 1 <= s.length <= 12.
Constraints
- 1 <= s.length <= 12.
- s consists of digit characters only.
- Every character must be consumed and the result must contain exactly four octets.
- A string shorter than 4 or longer than 12 characters can never form a valid IPv4 address.
Examples
Input: ("25525511135",)
Expected Output: True
Explanation: Splits as 255.255.11.135.
Input: ("0025555",)
Expected Output: True
Explanation: Splits as 0.0.255.55 (each leading '0' is a standalone octet).
Hints
- Each octet is 1 to 3 characters long, so an early length check (4 <= len <= 12) prunes impossible inputs.
- Backtrack over octet lengths 1, 2, 3; stop a branch as soon as the candidate octet is invalid (leading zero or > 255).
- After placing three dots, the fourth octet is simply the remaining suffix — accept only if that suffix is itself a valid octet.
Restore All Valid IPv4 Addresses
Given a string `s` of digits, return a list of all valid IPv4 addresses that can be formed by inserting exactly three dots into `s`. You must use every digit of `s`, and each resulting address must follow standard IPv4 rules:
- Exactly four octets, each an integer in [0, 255].
- No leading zeros in an octet unless the octet is exactly "0".
Return the addresses in any order, with no duplicates. (Sorting the result gives a deterministic order.)
Example:
- "25525511135" -> ["255.255.11.135", "255.255.111.35"]
Constraint: 1 <= s.length <= 12.
Constraints
- 1 <= s.length <= 12.
- s consists of digit characters only.
- Every digit must be used; each address has exactly four octets.
- The returned list contains no duplicate addresses.
Examples
Input: ("25525511135",)
Expected Output: ["255.255.11.135", "255.255.111.35"]
Explanation: The two ways to place dots that keep every octet <= 255 without leading zeros.
Input: ("0000",)
Expected Output: ["0.0.0.0"]
Explanation: Each zero must stand alone, giving a single address.
Hints
- Backtrack by trying octet lengths of 1, 2, and 3 at each of the four positions.
- Prune a branch immediately when an octet has a leading zero (and length > 1) or exceeds 255.
- Only record a candidate when you have placed four octets AND consumed the entire string; sort the collected results for a stable output order.