LeetCode 93: Restore IP Addresses Solution

Master LeetCode problem 93 (Restore IP Addresses), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

93. Restore IP Addresses

Medium

String Backtracking

Problem Explanation

Explanation:

To solve this problem, we can use a backtracking approach. We will try all possible combinations of valid IP addresses by placing dots at different positions in the given string. At each step, we check if the current substring forms a valid IP address. If it does, we recursively explore placing dots at the next positions. We keep track of the valid IP addresses we have found so far.

Backtracking Algorithm:
- Start with an empty list to store valid IP addresses.
- Perform backtracking starting from the beginning of the input string.
- At each step, try placing a dot after 1, 2, or 3 characters (as long as these characters form a valid integer between 0 and 255).
- Continue recursively until we have placed all 3 dots.
- If we have successfully placed all 3 dots and the remaining substring forms a valid integer, add it to the list of valid IP addresses.
- Backtrack to explore other possibilities.
Time Complexity:
- The worst-case time complexity is O(3^4) as we can place a dot after each of the 3 possible lengths (1, 2, or 3) for each of the 4 parts of the IP address.
Space Complexity:
- The space complexity is O(1) for the output list of valid IP addresses and O(n) for the recursive call stack, where n is the length of the input string. :

Solution Code

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        backtrack(result, s, 0, "", 0);
        return result;
    }
    
    private void backtrack(List<String> result, String s, int index, String current, int count) {
        if (count > 4) return;
        if (count == 4 && index == s.length()) {
            result.add(current);
            return;
        }
        
        for (int i = 1; i <= 3; i++) {
            if (index + i > s.length()) break;
            String segment = s.substring(index, index + i);
            if ((segment.startsWith("0") && segment.length() > 1) || (i == 3 && Integer.parseInt(segment) > 255)) continue;
            backtrack(result, s, index + i, current + segment + (count == 3 ? "" : "."), count + 1);
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 93 (Restore IP Addresses)?

This page provides optimized solutions for LeetCode problem 93 (Restore IP Addresses) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 93 (Restore IP Addresses)?

The time complexity for LeetCode 93 (Restore IP Addresses) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 93 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 93 in Java, C++, or Python.

Back to LeetCode Solutions