All problems

Restore IP Addresses

Medium · backtracking

An IPv4 address is written as four numbers separated by dots, like 192.168.0.1. Each number is a whole number from 0 to 255 written in plain digits with no leading zeros: 0 is allowed, but 00 and 07 are not.

You are given a text s made only of digits, from which all the dots were removed. Put exactly three dots back into s so that it becomes a valid address. You may not remove, add, reorder or change any digit.

Return every valid address you can make, each as text. Two addresses are different if the dots are in different places. They may be returned in any order. If no valid address exists, return an empty list.

Examples

Example 1

Input: s = "25525511135"

Output: ["255.255.11.135", "255.255.111.35"]

Both place the dots so that every number is at most 255. Other splits, such as 255.255.1.1135, have a number that is too big.

Example 2

Input: s = "010010"

Output: ["0.10.0.10", "0.100.1.0"]

A number may be 0 on its own, but 01 or 010 would have a leading zero, so the first number must be exactly 0.

Example 3

Input: s = "999"

Output: []

Four numbers need at least four digits.

Constraints