Restore IP Addresses
Medium · Backtracking · Explanation and code example
Iteration
How it works
Since there are exactly four segments and each can have 1, 2, or 3 characters, we can enumerate all 81 combinations (3^4) of segment lengths directly. For each combination, we check if the total length matches the input string and whether each resulting segment is valid. This avoids recursion overhead while still exploring all possibilities.
Steps
- If the string length exceeds 12, return an empty list.
- Use four nested loops, each iterating from 1 to 3 (representing segment lengths
seg1,seg2,seg3,seg4). - If the sum of all four segment lengths does not equal the string length, skip this combination.
- Extract the four substrings based on the current segment lengths.
- Validate each segment: no leading zeros (unless single digit) and value <= 255.
- If all segments are valid, join them with dots and add to
res. - Return all valid IP addresses found.
Complexity
- Time complexity:
O(m ^ n * n) - Space complexity:
O(m * n)
Where
mis equals to3as there are at most three digits in a valid segment andnis equals to4as there are four segments in a valid IP.
Things to watch for
Allowing Leading Zeros in Multi-Digit Segments
Segments like "01" or "001" are invalid in IP addresses, but "0" alone is valid. The validation must specifically reject multi-digit segments that start with zero while accepting single-digit zeros.
Missing the Upper Bound Check for Segment Values
Each segment must be at most 255. Forgetting to check this constraint or using < 256 instead of <= 255 can lead to subtle bugs, especially for three-digit segments like "256" which appear valid at first glance.
Not Validating Total String Length Early
An IP address can have at most 12 digits (four segments of 3 digits each) and at least 4 digits (four segments of 1 digit each). Failing to check these bounds upfront leads to unnecessary computation on inputs that cannot possibly form valid IPs.
Python code example
from typing import List
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
res = []
if len(s) > 12:
return res
def valid(num):
return len(num) == 1 or (int(num) < 256 and num[0] != "0")
def add(s1, s2, s3, s4):
if s1 + s2 + s3 + s4 != len(s):
return
num1 = s[:s1]
num2 = s[s1:s1+s2]
num3 = s[s1+s2:s1+s2+s3]
num4 = s[s1+s2+s3:]
if valid(num1) and valid(num2) and valid(num3) and valid(num4):
res.append(num1 + "." + num2 + "." + num3 + "." + num4)
for seg1 in range(1, 4):
for seg2 in range(1, 4):
for seg3 in range(1, 4):
for seg4 in range(1, 4):
add(seg1, seg2, seg3, seg4)
return res
C++ code example
class Solution {
public:
vector<string> restoreIpAddresses(string s) {
vector<string> res;
if (s.size() > 12) return res;
auto valid = [&](string& num) {
if (num.size() > 1 && num[0] == '0') return false;
int value = stoi(num);
return value <= 255;
};
for (int seg1 = 1; seg1 < 4; ++seg1) {
for (int seg2 = 1; seg2 < 4; ++seg2) {
for (int seg3 = 1; seg3 < 4; ++seg3) {
for (int seg4 = 1; seg4 < 4; ++seg4) {
if (seg1 + seg2 + seg3 + seg4 != s.size()) continue;
string num1 = s.substr(0, seg1);
string num2 = s.substr(seg1, seg2);
string num3 = s.substr(seg1 + seg2, seg3);
string num4 = s.substr(seg1 + seg2 + seg3);
if (valid(num1) && valid(num2) && valid(num3) && valid(num4)) {
res.push_back(num1 + "." + num2 + "." + num3 + "." + num4);
}
}
}
}
}
return res;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.