Validate and restore IPv4 addresses
Overview
This question evaluates string processing, strict input validation rules, and constrained combinatorial search skills (e.g., backtracking) for generating and verifying IPv4 addresses.
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).