algoadvance

Leetcode 93. Restore IP Addresses

Problem Statement

Given a string containing only digits, restore it by returning all possible valid IP address combinations that can be formed by inserting dots into the string. A valid IP address consists of exactly four integers (each between 0 and 255) separated by single dots and cannot have leading zeros.

Example:

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

Clarifying Questions

  1. Input Constraints:
    • Is the length of the input string fixed?
    • Are there any constraints on the input string being too large?
  2. Output Format:
    • Should the output be in any specific order?

Code

import java.util.ArrayList;
import java.util.List;

public class RestoreIPAddresses {

    public static void main(String[] args) {
        String input = "25525511135";
        List<String> result = restoreIpAddresses(input);
        for (String ip : result) {
            System.out.println(ip);
        }
    }

    public static List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        if (s == null || s.length() < 4 || s.length() > 12) {
            return result;
        }
        backtrack(s, 0, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(String s, int start, List<String> current, List<String> result) {
        if (current.size() == 4) {
            if (start == s.length()) {
                result.add(String.join(".", current));
            }
            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) || (len == 3 && Integer.valueOf(segment) > 255)) {
                continue;
            }

            current.add(segment);
            backtrack(s, start + len, current, result);
            current.remove(current.size() - 1);
        }
    }
}

Strategy

  1. Backtracking:
    • Use a recursive backtracking approach to generate all possible IP addresses.
    • Start from the beginning of the string and attempt to place dots.
    • Each recursive call attempts to create every possible segment of the IP address.
    • Base case: When four segments are created, check if the entire string has been used.
  2. Segment Validation:
    • A valid segment is between 0 and 255 and does not have leading zeros unless it is exactly “0”.
    • Use substring and checks to validate each segment before recursively calling the function.
  3. Recursion Control:
    • Ensure the recursion does not go out of bounds or generate invalid segments through proper conditions checks.

Time Complexity

The time complexity is ( O(3^4) ) because for each of the 4 segments, there are at most 3 possibilities (1-digit, 2-digit, or 3-digit segments). So, the overall complexity can be considered polynomial given the limited number of segments (4 in this case). Hence, it is manageable for valid input lengths (4-12 characters).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI