Leetcode 93: Restore IP Addresses (Java Backtracking Solution)

A valid IP address consists of exactly four integers (0–255), separated by dots. Leading zeros are not allowed unless the number is just "0".

Examples:

• ✅ Valid: 192.168.1.1, 0.1.2.201
• ❌ Invalid: 0.011.255.245, 192.168.1.312, 192.168@1.1

🧠 Problem Statement

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting three dots. You can't reorder or remove any digits.

📥 Input:

📤 Output:

🔍 Intuition Behind the Solution

The key idea is to insert **3 dots** to split the string into **4 valid parts**, and ensure each part is between 0 and 255 and doesn’t contain leading zeros.

🚀 Backtracking Approach

We'll recursively place dots after 1, 2, or 3 characters, and backtrack if the segment is invalid.

Rules for Valid Segments:

1. Length between 1 to 3
2. Cannot start with '0' unless it’s exactly "0"
3. Integer value must be between 0 and 255

🧪 Java Code - Restore IP Addresses with Backtracking

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        backtrack(s, 0, "", 0, result);
        return result;
    }

    private void backtrack(String s, int index, String currentIP, int dots, List<String> result) {
        if (dots == 4 && index == s.length()) {
            result.add(currentIP.substring(0, currentIP.length() - 1)); // remove last dot
            return;
        }

        if (dots > 4) return;

        for (int len = 1; len <= 3; len++) {
            if (index + len > s.length()) break;

            String segment = s.substring(index, index + len);
            if (isValid(segment)) {
                backtrack(s, index + len, currentIP + segment + ".", dots + 1, result);
            }
        }
    }

    private boolean isValid(String s) {
        if (s.length() > 1 && s.charAt(0) == '0') return false;
        int val = Integer.parseInt(s);
        return val >= 0 && val <= 255;
    }
}

🔍 Dry Run

Input: "25525511135"

• Try placing first dot after 3 digits: "255."
• Second part: "255."
• Third part: "11."
• Last part: "135" → Valid!

One valid IP: 255.255.11.135

⏱ Time and Space Complexity

• Time Complexity: O(1) — bounded because max combinations = 3³ = 27
• Space Complexity: O(n) for recursion stack and result list

🧠 Summary

• Use backtracking to place 3 dots
• Validate each segment immediately
• Prune recursion when invalid or too long

📚 Related Problems

• 131. Palindrome Partitioning
• 78. Subsets
• 46. Permutations

🎯 Final Thoughts

Mastering this problem boosts your ability to break strings into valid structures and control recursion depth wisely. Backtracking gives you fine-grained control over trial-and-error logic in computational problems like this.

Leetcode 93. Restore IP Addresses - Java Recursive Solution

class Solution {
    private boolean valid(String s, int start, int length) {
        return length == 1 || 
            (s.charAt(start) != '0' && 
             (length < 3 || 
              s.substring(start, start + length).compareTo("255") <= 0));
    }

    private void helper(String s, int startIndex, List dots, List ans) {
        final int remainingLength = s.length() - startIndex;
        final int remainingParts = 4 - dots.size();
        if (remainingLength > remainingParts * 3 || remainingLength < remainingParts) {
            return;
        }
        if (dots.size() == 3) {
            if (valid(s, startIndex, remainingLength)) {
                StringBuilder sb = new StringBuilder();
                int last = 0;
                for (Integer dot : dots) {
                    sb.append(s, last, last + dot).append('.');
                    last += dot;
                }
                sb.append(s.substring(startIndex));
                ans.add(sb.toString());
            }
            return;
        }
        for (int curLen = 1; curLen <= 3 && curLen <= remainingLength; ++curLen) {
            if (valid(s, startIndex, curLen)) {
                dots.add(curLen);
                helper(s, startIndex + curLen, dots, ans);
                dots.remove(dots.size() - 1);
            }
        }
    }

    public List restoreIpAddresses(String s) {
        List ans = new ArrayList<>();
        helper(s, 0, new ArrayList<>(), ans);
        return ans;
    }
}
  

Leetcode 93. Restore IP Addresses - Java Iterative Solution

class Solution {
    private boolean isValidSegment(String s, int start, int length) {
        boolean isSingleDigit = length == 1;
        boolean noLeadingZero = s.charAt(start) != '0';
        boolean lessThan255 = length < 3 || s.substring(start, start + length).compareTo("255") <= 0;
        return isSingleDigit || (noLeadingZero && lessThan255);
    }

    public List restoreIpAddresses(String s) {
        List ans = new ArrayList<>();
        int n = s.length();
        for (int len1 = Math.max(1, n - 9); len1 <= 3 && len1 <= n - 3; len1++) {
            if (!isValidSegment(s, 0, len1)) continue;
            for (int len2 = Math.max(1, n - len1 - 6); len2 <= 3 && len2 <= n - len1 - 2; len2++) {
                if (!isValidSegment(s, len1, len2)) continue;
                for (int len3 = Math.max(1, n - len1 - len2 - 3); len3 <= 3 && len3 <= n - len1 - len2 - 1; len3++) {
                    int len4 = n - len1 - len2 - len3;
                    if (len4 < 1 || len4 > 3) continue;
                    if (isValidSegment(s, len1 + len2, len3) &&
                        isValidSegment(s, len1 + len2 + len3, len4)) {
                        String ip = String.join(".",
                            s.substring(0, len1),
                            s.substring(len1, len1 + len2),
                            s.substring(len1 + len2, len1 + len2 + len3),
                            s.substring(len1 + len2 + len3));
                        ans.add(ip);
                    }
                }
            }
        }
        return ans;
    }
}
  

Leetcode 93. Restore IP Addresses - JavaScript Solution

/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function(s) {
    const res = [];
    function backtrack(start, path, dotCount) {
        if (start === s.length && dotCount === 4) {
            res.push(path.slice(0, -1));
            return;
        }
        if (start >= s.length || dotCount > 4) return;
        for (let i = start; i < start + 3 && i < s.length; i++) {
            const segment = s.substring(start, i + 1);
            if (isValid(segment)) {
                backtrack(i + 1, path + segment + '.', dotCount + 1);
            }
        }
    }

    function isValid(str) {
        if (str.length > 1 && str[0] === '0') return false;
        if (parseInt(str) > 255) return false;
        return true;
    }

    backtrack(0, '', 0);
    return res;
};