231. Generate All Valid IP Addresses from a String of Digits

Given a string s of digits, insert exactly three dots into it to split it into four segments forming a valid IPv4 address. Each segment must be non-empty, at most 3 digits long, represent an integer between 0 and 255, and must not have a leading zero unless the segment is exactly '0'. Print every valid IP address obtainable this way, space-separated, in the order produced by trying the first segment's length from 1 to 3, then (for each) the second segment's length from 1 to 3, then the third segment's length from 1 to 3 (the fourth segment takes whatever digits remain). If none exist, print 'None'.

Input: A single line containing the digit string s. Output: Print every valid IP address obtainable from s, space-separated on one line in the specified segment-length generation order, or print 'None' if no valid IP exists.

4 <= |s| <= 12, s consists of digits '0'-'9'

The 'no leading zero unless the segment is exactly 0' rule is the most commonly mis-implemented validity check - segments like '01' or '00' must be rejected even though they're numerically small enough to be in range.

Given a string of digits, insert three dots to split it into four valid IPv4 segments, and print every way this can be done correctly. Brute force: This problem's very nature IS trying every combination of segment lengths - there's no way to avoid exploring the (at most 3*3*3=27) length combinations for the first three segments, since the fourth is always determined by what's left; the key skill is validating each candidate efficiently and correctly. Optimised: Since each of the first three segments can only be 1, 2, or 3 digits long, there are at most 27 combinations to try total (a small, FIXED upper bound, not exponential in the string's length) - trying all of them and validating each segment's numeric range and leading-zero rule directly is both simple and efficient given this small search space.

Consider every possible way to place three dot positions among the string's index gaps (all combinations of three cut points), slice the string into four pieces for each combination, and check whether each piece independently satisfies the segment rules (length 1-3, value 0-255, no invalid leading zero). This checks far more candidate splits than necessary, including ones where an early segment is already obviously too long or too short. Time: O(n^3) candidate splits, each validated in O(n) Space: O(n) per candidate

Restrict each of the four segments to only try lengths 1, 2, or 3 (instead of arbitrary cut positions), recursively choosing each segment's length in turn, but only validate a segment's numeric range and leading-zero rule after all four segments have been fully chosen. This shrinks the branching factor to at most 3 per segment (3^4 leaves total) but still wastes work fully constructing and slicing invalid combinations before rejecting them. Time: O(3^4 * n) Space: O(n)

Same bounded-length backtracking, but validate each segment (leading zero, value <= 255) immediately as it is formed and also check that the digits remaining after it can still be evenly divided among the remaining segments (each needing 1-3 digits) before recursing further. This prunes invalid or infeasible branches the moment they become invalid rather than after building the full candidate, so almost no wasted recursive calls are made beyond the handful of genuinely valid IP addresses. Time: O(3^4) Space: O(n)

1. Try every possible length (1, 2, or 3 digits) for the first segment. 2. For each choice, try every possible length for the second segment, then the third. 3. The fourth segment automatically takes whatever digits remain. 4. For each of the four segments, check it's valid (1-3 digits, numeric value 0-255, and no leading zero unless the segment is exactly '0') before accepting the full combination.

Time: O(1) effectively, since there are at most 27 combinations to check regardless of input size (bounded by the fixed 4-segment IPv4 structure), each validated in constant time. Space: O(number of valid IP addresses found), for storing the results.

Test with |s|=4 (minimum, e.g. "1111"), |s|=12 (maximum, all four segments 3 digits), digit strings containing '0' that could force an invalid leading zero, and a string for which no valid IP can be formed at all.

Be ready to state the tight bound explicitly (at most 3 choices per segment, 3 segments to choose freely, so at most 27 total combinations) - recognizing this small fixed search space is what makes brute-force enumeration the RIGHT approach here, not a compromise.