Validate and restore 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).

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.

Hints

1. Split on '.' and immediately reject if you do not get exactly four parts.
2. Use a digits-only check (e.g. str.isdigit()) to rule out signs, spaces, and empty octets in one shot.
3. 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.

Hints

1. Each octet is 1 to 3 characters long, so an early length check (4 <= len <= 12) prunes impossible inputs.
2. Backtrack over octet lengths 1, 2, 3; stop a branch as soon as the candidate octet is invalid (leading zero or > 255).
3. 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.

Hints

1. Backtrack by trying octet lengths of 1, 2, and 3 at each of the four positions.
2. Prune a branch immediately when an octet has a leading zero (and length > 1) or exceeds 255.
3. Only record a candidate when you have placed four octets AND consumed the entire string; sort the collected results for a stable output order.