Restore IP Addresses - Practice Coding Problems

Restore IP Addresses - Problem

String Backtracking Medium

A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.

For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "[email protected]" are invalid IP addresses.

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.

Input & Output

Example 1 — Basic Case

$ Input: s = "25525511135"

› Output: ["255.255.11.135","255.255.111.35"]

💡 Note: Two valid IP addresses can be formed: 255.255.11.135 and 255.255.111.35. Each segment is between 0-255 with no leading zeros.

Example 2 — No Valid IPs

$ Input: s = "0000"

› Output: ["0.0.0.0"]

💡 Note: Only one valid IP can be formed: 0.0.0.0. Each segment is exactly '0' which is valid.

Example 3 — Leading Zero Issue

$ Input: s = "101023"

› Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

💡 Note: Multiple valid combinations exist. Note that segments like '010' are invalid due to leading zeros.

Constraints

1 ≤ s.length ≤ 20
s consists of digits only

Visualization

Tap to expand

Understanding the Visualization

Input

String of digits that need to be split into 4 IP segments

Split & Validate

Try all ways to place 3 dots, validate each segment

Output

Return all valid IP address combinations

Key Takeaway

🎯 Key Insight: Use backtracking to systematically try all segment combinations while validating IP rules

Asked in

F Facebook 35 G Google 25 a Amazon 20

The key insight is that each IP segment must be 0-255 with no leading zeros (except '0' itself). Backtracking provides the optimal approach by systematically trying all valid segment lengths while pruning invalid paths early. Time: O(3⁴), Space: O(4)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(n³)	O(1)	Try all possible ways to place 3 dots in the string
Backtracking - Systematic Exploration	O(3⁴)	O(4)	Use backtracking to build valid IP addresses segment by segment

Brute Force - Try All Combinations — Algorithm Steps

Try all positions for first dot
Try all positions for second dot
Try all positions for third dot
Validate each 4-segment combination

Visualization

Tap to expand

Step-by-Step Walkthrough

Input

String of digits to split into IP segments

Try Positions

Test all combinations of dot positions

Validate

Check if each segment forms valid IP part

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int isValid(char* segment) {
    int len = strlen(segment);
    if (len == 0 || len > 3) return 0;
    if (len > 1 && segment[0] == '0') return 0;
    int num = atoi(segment);
    return num >= 0 && num <= 255;
}

int min(int a, int b) {
    return a < b ? a : b;
}

int main() {
    char s[20];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char result[1000][20];
    int count = 0;
    int n = strlen(s);
    
    for (int i = 1; i < min(4, n); i++) {
        for (int j = i + 1; j < min(i + 4, n); j++) {
            for (int k = j + 1; k < min(j + 4, n); k++) {
                if (k < n) {
                    char seg1[4], seg2[4], seg3[4], seg4[4];
                    strncpy(seg1, s, i); seg1[i] = '\0';
                    strncpy(seg2, s + i, j - i); seg2[j - i] = '\0';
                    strncpy(seg3, s + j, k - j); seg3[k - j] = '\0';
                    strcpy(seg4, s + k);
                    
                    if (isValid(seg1) && isValid(seg2) && isValid(seg3) && isValid(seg4)) {
                        sprintf(result[count], "%s.%s.%s.%s", seg1, seg2, seg3, seg4);
                        count++;
                    }
                }
            }
        }
    }
    
    printf("[");
    for (int i = 0; i < count; i++) {
        printf("\"%s\"", result[i]);
        if (i < count - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops to try all dot positions, with constant validation work

⚠ Quadratic Growth

Space Complexity

O(1)

Only stores result list, no extra space for algorithm itself

✓ Linear Space

185.0K Views

Medium Frequency

~25 min Avg. Time

3.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler