185. Restore IP Addresses

Medium · Backtracking

A valid IPv4 address consists of four numbers (octets) separated by dots, where each number is between 0 and 255 inclusive, and has no leading zeros (except for "0" itself). Given a string of digits, find all valid IPv4 addresses that can be formed by inserting exactly three dots to partition the string into four parts. Each part must be a valid octet. Return the results as an array of strings sorted in ascending order.

Input: a string `s` containing only digits. Output: an array of valid IPv4 addresses (as strings) in sorted ascending order.

Examples

Example 1
Input: "25525511135"
Output: ["255.255.11.135","255.255.111.35"]
Explanation: Two valid IPs
Example 2
Input: "0000"
Output: ["0.0.0.0"]
Explanation: Each octet is a single zero

Constraints