DSA 450 Notes

Problem Statement

Given a string containing only digits, generate all possible valid IP addresses that can be formed by inserting dots. A valid IP address consists of exactly four integers (each from 0 to 255) separated by single dots, and cannot have leading zeros (except for the number 0 itself).

Example:

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

Example 2:

Input: "0000"
Output: ["0.0.0.0"]

Approach 1: Brute Force (Three Loops)

Intuition

An IP address has exactly 4 parts. Place 3 dots at all possible positions and validate each resulting IP address.

Algorithm

Try all positions for the first dot (1 to min(3, n-3))
Try all positions for the second dot
Try all positions for the third dot
Validate each of the 4 parts
If valid, add to result

java

import java.util.*;

public class Solution {
    private boolean isValid(String s) {
        if (s.isEmpty() || s.length() > 3) return false;
        if (s.length() > 1 && s.charAt(0) == '0') return false;
        int num = Integer.parseInt(s);
        return num >= 0 && num <= 255;
    }
    
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        int n = s.length();
        
        if (n < 4 || n > 12) return result;
        
        for (int i = 1; i <= 3 && i < n; i++) {
            for (int j = i + 1; j <= i + 3 && j < n; j++) {
                for (int k = j + 1; k <= j + 3 && k < n; k++) {
                    String part1 = s.substring(0, i);
                    String part2 = s.substring(i, j);
                    String part3 = s.substring(j, k);
                    String part4 = s.substring(k);
                    
                    if (isValid(part1) && isValid(part2) && 
                        isValid(part3) && isValid(part4)) {
                        result.add(part1 + "." + part2 + "." + 
                                  part3 + "." + part4);
                    }
                }
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(1) - Maximum 81 combinations (3³ * 3)
Space Complexity: O(1) - Not counting output

Approach 2: Backtracking (Optimal for Clarity)

Intuition

Use backtracking to build the IP address part by part. At each step, try adding 1, 2, or 3 digits as the next part.

Algorithm

Start with empty current IP and 0 parts
At each step, try taking 1-3 characters as the next part
If valid, add to current and recurse
When 4 parts are formed and string is exhausted, add to result
Backtrack and try other combinations

java

import java.util.*;

public class Solution {
    private void backtrack(String s, int start, List<String> current, 
                          List<String> result) {
        // If we have 4 parts and used all characters
        if (current.size() == 4) {
            if (start == s.length()) {
                result.add(String.join(".", current));
            }
            return;
        }
        
        // Pruning
        int remaining = s.length() - start;
        int partsNeeded = 4 - current.size();
        if (remaining < partsNeeded || remaining > partsNeeded * 3) {
            return;
        }
        
        // Try taking 1, 2, or 3 characters
        for (int len = 1; len <= 3 && start + len <= s.length(); len++) {
            String part = s.substring(start, start + len);
            
            // Check for leading zeros
            if (part.length() > 1 && part.charAt(0) == '0') continue;
            
            // Check range
            if (Integer.parseInt(part) > 255) continue;
            
            current.add(part);
            backtrack(s, start + len, current, result);
            current.remove(current.size() - 1);
        }
    }
    
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), result);
        return result;
    }
}

Complexity Analysis

Time Complexity: O(3⁴) = O(81) = O(1) - At most 81 combinations
Space Complexity: O(1) - Not counting output, just recursion stack of depth 4

Edge Cases and Validation

Dry Run Example

Input: "25525511135"

Backtracking:
├── part1 = "2"
│   ├── part2 = "5" -> remaining = 9, need 2 parts -> max 6, skip
│   ├── part2 = "55" -> remaining = 7, need 2 parts -> max 6, skip
│   └── part2 = "552" -> remaining = 6, need 2 parts -> ok
│       ├── part3 = "5" ...
│       └── ...
├── part1 = "25"
│   └── ...
└── part1 = "255"
    ├── part2 = "2" ...
    ├── part2 = "25" ...
    └── part2 = "255"
        ├── part3 = "1" -> part4 = "1135" > 255, invalid
        ├── part3 = "11" -> part4 = "135", valid! -> "255.255.11.135"
        └── part3 = "111" -> part4 = "35", valid! -> "255.255.111.35"

Output: ["255.255.11.135", "255.255.111.35"]

Key Takeaways

Constant time complexity - Despite recursion, max iterations are bounded
Pruning is crucial - Skip invalid branches early (remaining chars check)
Leading zeros are tricky - "01" is invalid, but "0" is valid
Three nested loops is cleaner for this specific problem
Backtracking approach is more generalizable
This is a common interview problem testing string manipulation and validation

Program to generate all possible valid IP addresses from given string

Problem Statement

Approach 1: Brute Force (Three Loops)

Intuition

Algorithm

Complexity Analysis

Approach 2: Backtracking (Optimal for Clarity)

Intuition

Algorithm

Complexity Analysis

Edge Cases and Validation

Dry Run Example

Key Takeaways