The O(n) Club: Restore IP Addresses—Dotting Your Way to Sanity

The O(n) Club: Restore IP Addresses—Dotting Your Way to Sanity

⚡ TL;DR

Stuff three dots into a digit string until you get every possible valid IPv4 address. Four segments, 0–255, no sneaky leading zeros (unless it’s ‘0’). If you’re into wasting cycles, brute force all combos—otherwise, backtracking rescues your CPU temps:

// Java: Backtracking FTW
public List<String> restoreIpAddresses(String s) {
    List<String> result = new ArrayList<>();
    backtrack(s, 0, new ArrayList<>(), result);
    return result;
}

🧠 How Devs Usually Mess This Up

Some folks let “012.34.56.078” slip through and call it an IP—mission failed. Classic goofs:

• Accepting segments like “04” or “256” (Hint: 256 is a fake friend, so is anything with leading zeros).
• Losing track of dots and inventing a fifth segment— imagine 192.16.8.0.5.1 (router says nope).
• Rearranging digits or skipping some. It’s restoration, not a puzzle game.
• Letting “0.0.0.00” pass (just… why?).

🔍 What’s Actually Going On

This is string surgery: you must carve three neatly placed dots so that every piece (segment) is between 0 and 255. Don’t let ’04’ or ’00’ sneak into your masterpiece. The fun part? Try slicing after 1, 2, or 3 digits at each step—then recursively go deeper. If you end up with exactly four solid segments and zero leftover numbers, congrats! Any extra digits or broken rules? Back up and take a different cut.

Backtracking here is like giving a robot chef unlimited ingredients and a strict recipe—if the meal turns out gross, the chef starts again with the same groceries.

🛠️ PseudoCode

• Reject impossible lengths: If s.length() < 4 or s.length() > 12, bail immediately. You can’t squish or stretch to fit.
• Backtrack: For each of 1, 2, 3 digits, cut a segment.
• Validate with no remorse: reject if segment has leading zeros or is >255.
• Add segment to the list; recurse on the rest.
• If you have four segments and used every digit: join with dots and store.
• Otherwise, back up, pop segment, and try the next split.

// Java backtrack core
if (segments.size() == 4 && pos == s.length()) add result;
for (int len = 1; len <= 3; len++) {
  if (pos + len > s.length()) break;
  String seg = s.substring(pos, pos + len);
  if (isValid(seg)) {
    segments.add(seg);
    backtrack(...);
    segments.remove(segments.size() - 1);
  }
}

💻 The Code

public List<String> restoreIpAddresses(String s) {
    List<String> result = new ArrayList<>();
    if (s.length() < 4 || s.length() > 12) return result;
    backtrack(s, 0, new ArrayList<>(), result);
    return result;
}
 private void backtrack(String s, int pos, List<String> segments, List<String> result) {
    if (segments.size() == 4) {
        if (pos == s.length())
            result.add(String.join(".", segments));
        return;
    }
    for (int len = 1; len <= 3; len++) {
        if (pos + len > s.length()) break;
        String seg = s.substring(pos, pos + len);
        if (isValid(seg)) {
            segments.add(seg);
            backtrack(s, pos + len, segments, result);
            segments.remove(segments.size() - 1);
        }
    }
}
 private boolean isValid(String seg) {
    if (seg.length() > 1 && seg.charAt(0) == '0') return false;
    int val = Integer.parseInt(seg);
    return val >= 0 && val <= 255;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Edge Cases: Reject length 12, segments like “00” or “256”, and sneaky input like “0000” (valid as “0.0.0.0” only).
• Performance: O(3^4), but prunes fast because most cuts are nonsense.
• Space: Don’t stress, unless you think your algorithm should process every IPv4 address ever used by humanity in real-time.

🧠 Interviewer Brain-Tattoo

“If your segments start with zero, your code’s a hacker’s best friend. Validate like your next job depends on it.”