609. Address Rebuilder
A network log lost the dots from some IPv4 addresses, leaving only the digits in the string digits. An address has exactly four numbers separated by dots, every number is between 0 and 255 inclusive, and a number may not have a leading zero unless it is exactly 0.
Return every valid address that can be made by inserting three dots into digits without removing, reordering or adding any digit. Each address must appear once and the addresses may be returned in any order. If none exists, return an empty array.
Example 1
- Input:
- digits = "172316"
- Output:
- ["1.7.23.16","1.7.231.6","1.72.3.16","1.72.31.6","17.2.3.16","17.2.31.6","17.23.1.6","172.3.1.6"]
- Explanation:
Several splits are valid, such as
17.23.1.6and172.3.1.6; each part stays within 0 to 255.
Example 2
- Input:
- digits = "0000"
- Output:
- ["0.0.0.0"]
- Explanation:
Only
0.0.0.0works, since parts like00would have a leading zero.
Example 3
- Input:
- digits = "999999"
- Output:
- ["9.9.99.99","9.99.9.99","9.99.99.9","99.9.9.99","99.9.99.9","99.99.9.9"]
- Explanation:
Every part would have to be larger than 255 or too short to use all digits, so no address exists.
Constraints
- 1 ≤
digits.length≤ 12 digitscontains only decimal digits.
How this problem is judged
- Answers
- The outer list may be in any order. Everything inside each item must match exactly.
Expected complexity
- Time
- O(3^4)
- Space
- O(1)