Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

93. Restore IP Addresses - Leetcode Solution

Code Implementation

class Solution:
    def restoreIpAddresses(self, s: str) -> list[str]:
        def backtrack(start, path):
            if len(path) == 4:
                if start == len(s):
                    res.append(".".join(path))
                return
            for l in range(1, 4):
                if start + l > len(s):
                    break
                segment = s[start:start + l]
                if (segment.startswith('0') and len(segment) > 1) or int(segment) > 255:
                    continue
                backtrack(start + l, path + [segment])
        res = []
        backtrack(0, [])
        return res
      
class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        vector<string> path;
        backtrack(s, 0, path, res);
        return res;
    }
private:
    void backtrack(const string& s, int start, vector<string>& path, vector<string>& res) {
        if (path.size() == 4) {
            if (start == s.size()) {
                res.push_back(path[0] + "." + path[1] + "." + path[2] + "." + path[3]);
            }
            return;
        }
        for (int len = 1; len <= 3; ++len) {
            if (start + len > s.size()) break;
            string segment = s.substr(start, len);
            if ((segment[0] == '0' && segment.length() > 1) || stoi(segment) > 255)
                continue;
            path.push_back(segment);
            backtrack(s, start + len, path, res);
            path.pop_back();
        }
    }
};
      
class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), res);
        return res;
    }
    private void backtrack(String s, int start, List<String> path, List<String> res) {
        if (path.size() == 4) {
            if (start == s.length()) {
                res.add(String.join(".", path));
            }
            return;
        }
        for (int len = 1; len <= 3; ++len) {
            if (start + len > s.length()) break;
            String segment = s.substring(start, start + len);
            if ((segment.startsWith("0") && segment.length() > 1) || Integer.parseInt(segment) > 255)
                continue;
            path.add(segment);
            backtrack(s, start + len, path, res);
            path.remove(path.size() - 1);
        }
    }
}
      
var restoreIpAddresses = function(s) {
    const res = [];
    function backtrack(start, path) {
        if (path.length === 4) {
            if (start === s.length) {
                res.push(path.join('.'));
            }
            return;
        }
        for (let len = 1; len <= 3; ++len) {
            if (start + len > s.length) break;
            const segment = s.substring(start, start + len);
            if ((segment.startsWith('0') && segment.length > 1) || Number(segment) > 255) continue;
            path.push(segment);
            backtrack(start + len, path);
            path.pop();
        }
    }
    backtrack(0, []);
    return res;
};

Problem Description

Given a string s containing only digits, return all possible valid IP address combinations that can be formed by inserting three dots into s. Each segment of the IP address must be a number between 0 and 255, and cannot have leading zeros (except for the number 0 itself). You must use every digit in s exactly once, and each solution must use a different placement of dots. No digit can be reused or omitted, and the order of digits must remain unchanged.

Thought Process

When first encountering this problem, it's tempting to try every possible way to split the string into four parts and check if each part is valid. However, brute-forcing every combination quickly becomes inefficient as the string grows longer. Instead, we can notice that:
  • Each IP segment must be at least 1 and at most 3 digits.
  • The entire string must be split into exactly 4 segments.
  • We can use backtracking to systematically try all possible segmentations, pruning paths early if they cannot possibly lead to a valid IP (for example, if a segment is too large or has leading zeros).
By thinking recursively and using backtracking, we avoid unnecessary work and only generate valid addresses.

Solution Approach

To solve this problem, we use a backtracking algorithm:
  1. Recursive Backtracking: We define a recursive function that keeps track of the current position in the string, the segments chosen so far, and the results list.
  2. Base Case: If we've chosen 4 segments and consumed all digits, we join the segments with dots and add them to the result list.
  3. Segment Selection: At each recursive call, we try to take 1, 2, or 3 digits from the current position (as long as there are enough digits left).
  4. Validation: We check if the chosen segment is valid:
    • It should not have leading zeros unless it is exactly '0'.
    • Its integer value should be between 0 and 255.
  5. Recursive Call: If the segment is valid, we recurse with the next position and the updated path.
  6. Backtracking: After the recursive call, we remove the last segment (backtrack) and try the next possibility.
This approach ensures we efficiently explore only valid segmentations and avoid unnecessary computation.

Example Walkthrough

Let's walk through the input s = "25525511135":
  • First, we try splitting as 2 | 5 | 5 | ...
  • We continue recursively, trying to form 4 segments.
  • One valid segmentation is 255 | 255 | 11 | 135, which forms "255.255.11.135".
  • Another valid segmentation is 255 | 255 | 111 | 35, which forms "255.255.111.35".
  • At each step, invalid segments (like "256" or "01") are skipped.
  • Ultimately, we return all possible valid IP addresses that use every digit exactly once and have valid segments.

Time and Space Complexity

  • Brute-force: There are up to O(n³) ways to place three dots in a string of length n, but many are invalid. For each, we check segment validity, which is O(1) per segment.
  • Optimized (Backtracking): The recursion depth is at most 4 (for 4 segments), and at each level, we try at most 3 choices (segment lengths). The total number of recursive calls is bounded and manageable for n ≤ 12 (since an IP address has at most 12 digits). Thus, the time complexity is O(1) for practical input sizes.
  • Space Complexity: O(1) auxiliary space (excluding the output list), as the recursion stack is at most 4 deep. The output list may contain up to dozens of results for small n.

Summary

This problem is elegantly solved using backtracking, which systematically explores all possible segmentations of the string into four valid IP address parts. By validating each segment and pruning invalid paths early, we avoid unnecessary computation and efficiently generate all valid results. The key insight is leveraging the properties of IP addresses (segment length, value range, no leading zeros) to guide the recursion and ensure correctness.