Restore IP Addresses

Problem

Given a digit string, return every valid IPv4 address by inserting exactly 3 dots. A valid octet is 0-255 with no leading zeros.

Constraints

• 1 ≤ s.length ≤ 20

Approach — Backtracking

This is a Backtracking problem. The idea: build candidates one choice at a time and abandon a branch the moment it can't lead to a valid answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: exponential worst case.

Solution code

Python

class Solution:
    def restoreIpAddresses(self, s):
        res = []
        def bt(start, parts):
            if len(parts) == 4:
                if start == len(s):
                    res.append('.'.join(parts))
                return
            for ln in range(1, 4):
                if start + ln > len(s):
                    break
                seg = s[start:start+ln]
                if (seg[0] == '0' and ln > 1) or int(seg) > 255:
                    continue
                bt(start + ln, parts + [seg])
        bt(0, [])
        return res

Java

import java.util.*;
class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> out = new ArrayList<>();
        bt(out, s, 0, 0, new StringBuilder());
        return out;
    }
    private void bt(List<String> out, String s, int i, int parts, StringBuilder cur) {
        if (parts == 4) { if (i == s.length()) out.add(cur.substring(0, cur.length() - 1)); return; }
        for (int len = 1; len <= 3 && i + len <= s.length(); len++) {
            String seg = s.substring(i, i + len);
            if ((seg.length() > 1 && seg.charAt(0) == '0') || Integer.parseInt(seg) > 255) continue;
            int before = cur.length();
            cur.append(seg).append('.');
            bt(out, s, i + len, parts + 1, cur);
            cur.setLength(before);
        }
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.