IP Addresses From a Digit String

Medium

An IP address is four integers from 0 to 255 joined by dots. Leading zeros are not allowed: "0" is fine, but "01" or "00" is not. For example, "10.0.255.7" is a valid address, while "10.256.1.1" and "10.01.1.1" are not. The dots got lost from an address, leaving only the string of digits digits. Return every valid IP address you can get by inserting three dots into it. You may not reorder, remove or add digits. The addresses may be returned in any order.

Example 1

digits='10010' → ['1.0.0.10', '10.0.1.0']

"1.0.0.10" and "10.0.1.0" work. "100.1.0" has only three numbers, and "1.00.1.0" fails because of the leading zero in "00".

Example 2

digits='7001' → ['7.0.0.1']

With four digits every number is a single digit, so there is exactly one option, "7.0.0.1".

Example 3

digits='1234567890123' → []

Thirteen digits cannot fit into four numbers of at most three digits each, so there are no addresses.

Constraints

1 ≤ len(digits) ≤ 20
digits consists of digits only

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Backtracking

Similar problems

Keypad Words Medium All Balanced Bracket Strings Medium Word Traced on a Letter Grid Medium Cutting a Word Into Palindromes Medium Palindromes From a Set of Letters Medium

Input

digits='10010'

Expected

['1.0.0.10', '10.0.1.0']

Run checks the first 3 tests in your browser. Submit checks all 128 tests on the server, hidden ones included.