Restore the IP Addresses

An IPv4 address is four numbers separated by dots, like 192.168.0.1. Each number is between 0 and 255 and is written without leading zeros, so 0 is fine but 01 and 00 are not.

A log file lost the dots from its addresses, leaving only strings of digits. Write ip_addresses(digits) that returns every valid address you can make by putting exactly three dots into digits, keeping every digit in its original order. Return the addresses as a list of strings sorted in Python's normal string order, or an empty list if there are none.

Examples

ip_addresses("1111")    # returns ['1.1.1.1']
ip_addresses("101023")  # returns ['1.0.10.23', '1.0.102.3', '10.1.0.23', '10.10.2.3', '101.0.2.3']
ip_addresses("0000")    # returns ['0.0.0.0']
ip_addresses("123")     # returns []

Constraints

• 0 <= len(digits) <= 20
• digits contains only the characters 0 to 9.