Crack the Backend

Problem Statement

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. A valid IP address consists of four segments separated by dots, each segment is a number in [0, 255], and there are no leading zeros (except for the segment "0" itself). Return the answer in any order.

We need to split s into exactly 4 segments. Each segment has 1–3 digits and must be 0–255; if it has more than one digit, the first cannot be '0'. We backtrack: at segment seg and position start, try length 1, 2, or 3 (if the substring is valid), then recurse. When we have 4 segments and have consumed the whole string, we have one valid IP.

Key Observations

Backtracking: dfs(seg, start, path): if seg == 4 and start == s.length(), add path (join segments with '.') to the result. If seg == 4 (but start < n) or start >= n, return. For len = 1, 2, 3: if start + len <= s.length(), let token = s.substring(start, start+len). Check: no leading zero (token.length()>1 && token.charAt(0)=='0' → skip) and parseInt(token) <= 255. Then path.add(token), dfs(seg+1, start+len, path), path.remove.

Approach

High-level: DFS(seg, start, path). If seg==4 and start==len(s) add path joined by '.'. For len 1..3: if start+len<=n and segment s[start..start+len] is valid (0-255, no leading zero), path.add(segment), dfs(seg+1, start+len), path.remove.

Steps: Valid segment: length 1, or (length>1 and first char not '0') and value in [0,255]. dfs(seg, start): if seg==4 && start==s.length() add join(path). For len 1..3: token = s.substring(start, start+len); if valid, path.add(token), dfs(seg+1, start+len), path.remove.

Implementation

Java

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

void dfs(String s, int start, int seg, String path, List<String> result) {

    if (seg == 4 && start == s.length()) { result.add(path.substring(0, path.length()-1)); return; }
    if (seg == 4 || start >= s.length()) {
        return;
    }

    for (int len = 1; len <= 3 && start + len <= s.length(); len++) {
        String part = s.substring(start, start + len);

        if ((part.length()>1 && part.startsWith("0")) || Integer.parseInt(part) > 255) {
            continue;
        }

        dfs(s, start + len, seg + 1, path + part + ".", result);
    }
}

Test Cases

Example 1

Input

s = "25525511135"

Expected

["255.255.11.135","255.255.111.35"]

Explanation

Two valid IPs.

Complexity Analysis

Time: O(1) (at most 27 branches).
Space: O(1).

Follow-ups

Validate IP address string.