Restore IP Addresses

medium string backtracking

Problem

Given a string of digits, return all possible valid IPv4 addresses that can be formed by inserting dots. Each octet must be in [0, 255] and cannot have a leading zero (unless it is 0 itself).

Inputs = "25525511135"

Output["255.255.11.135","255.255.111.35"]

Backtrack over four octets, each 1–3 digits long.

def restore_ip_addresses(s):
    out, cur = [], []
    def valid(seg):
        if not seg or len(seg) > 3: return False
        if seg[0] == '0' and len(seg) > 1: return False
        return int(seg) <= 255
    def dfs(i):
        if len(cur) == 4:
            if i == len(s): out.append(".".join(cur))
            return
        for k in (1, 2, 3):
            if i + k > len(s): break
            seg = s[i:i + k]
            if valid(seg):
                cur.append(seg)
                dfs(i + k)
                cur.pop()
    dfs(0)
    return out

function restoreIpAddresses(s) {
  const out = [], cur = [];
  const valid = seg => seg.length >= 1 && seg.length <= 3 && !(seg[0] === '0' && seg.length > 1) && Number(seg) <= 255;
  function dfs(i) {
    if (cur.length === 4) { if (i === s.length) out.push(cur.join(".")); return; }
    for (let k = 1; k <= 3; k++) {
      if (i + k > s.length) break;
      const seg = s.slice(i, i + k);
      if (valid(seg)) { cur.push(seg); dfs(i + k); cur.pop(); }
    }
  }
  dfs(0);
  return out;
}

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> out = new ArrayList<>();
        dfs(s, 0, new ArrayList<>(), out);
        return out;
    }
    private void dfs(String s, int i, List<String> cur, List<String> out) {
        if (cur.size() == 4) { if (i == s.length()) out.add(String.join(".", cur)); return; }
        for (int k = 1; k <= 3; k++) {
            if (i + k > s.length()) break;
            String seg = s.substring(i, i + k);
            if (valid(seg)) { cur.add(seg); dfs(s, i + k, cur, out); cur.remove(cur.size() - 1); }
        }
    }
    private boolean valid(String seg) {
        if (seg.charAt(0) == '0') return seg.length() == 1;
        return Integer.parseInt(seg) <= 255;
    }
}

class Solution {
    bool valid(const string& seg) {
        if (seg[0] == '0') return seg.size() == 1;
        return stoi(seg) <= 255;
    }
    void dfs(const string& s, int i, vector<string>& cur, vector<string>& out) {
        if ((int)cur.size() == 4) {
            if (i == (int)s.size()) {
                string ip; for (int j = 0; j < 4; j++) { if (j) ip += '.'; ip += cur[j]; }
                out.push_back(ip);
            }
            return;
        }
        for (int k = 1; k <= 3; k++) {
            if (i + k > (int)s.size()) break;
            string seg = s.substr(i, k);
            if (valid(seg)) { cur.push_back(seg); dfs(s, i + k, cur, out); cur.pop_back(); }
        }
    }
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> out, cur;
        dfs(s, 0, cur, out);
        return out;
    }
};

Explanation

An IPv4 address is four numbers (octets) separated by dots, so the task is really: where do we place the three dots in the digit string? We try all the placements with backtracking.

The function dfs(i) starts at position i in the string and tries to cut off the next octet. An octet can be 1, 2, or 3 digits, so we loop k over those lengths, slice out seg, and check it with valid.

An octet is valid if it is at most 3 characters, is in the range 0..255, and has no leading zero (so "0" is fine but "01" is not). If a piece passes, we add it to cur, recurse to grab the next octet, then pop it off to try a different length.

We only record an answer when we have collected exactly 4 octets and have used up the entire string (i == len(s)) — otherwise leftover digits would mean an incomplete address.

Example: s = "25525511135". Two valid cuts exist: 255.255.11.135 and 255.255.111.35. Note that a piece like "256" would be rejected because it exceeds 255.

Time: O(3⁴) ≈ constant Space: O(1) aside from output