Skip to main content

70. Restore IP Addresses

mediumAsked at Snowflake

Generate all valid IP-address splits of a digit string. Snowflake asks this to test backtracking with multi-segment constraints — same shape as parsing dotted identifiers like db.schema.table.column.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake compiler-team uses this in onsites for identifier-parsing discussion.
  • LeetCode Discuss (2025-09)— Reported at Snowflake SDE-I screens.

Problem

A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros. Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s.

Constraints

  • 1 <= s.length <= 20
  • s consists of digits only.

Examples

Example 1

Input
s = "25525511135"
Output
["255.255.11.135","255.255.111.35"]

Example 2

Input
s = "0000"
Output
["0.0.0.0"]

Example 3

Input
s = "101023"
Output
["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

Approaches

1. Triple-nested loops

Try every (i, j, k) splitting into 4 segments. Validate each segment.

Time
O(1) (bounded by 81)
Space
O(1)
function restoreIpAddresses(s) {
  const result = [];
  for (let i = 1; i < 4 && i < s.length; i++) {
    for (let j = i + 1; j < i + 4 && j < s.length; j++) {
      for (let k = j + 1; k < j + 4 && k < s.length; k++) {
        const parts = [s.slice(0, i), s.slice(i, j), s.slice(j, k), s.slice(k)];
        if (parts.every(isValid)) result.push(parts.join('.'));
      }
    }
  }
  return result;
  function isValid(p) {
    if (p.length === 0 || p.length > 3) return false;
    if (p[0] === '0' && p.length > 1) return false;
    return parseInt(p, 10) <= 255;
  }
}

Tradeoff: Brute force but well-bounded. Works for n <= 20.

2. Backtracking with prune (optimal stylistically)

Backtrack picking 1-3 digits at each of 4 segments. Prune on invalid segments or wrong total length.

Time
O(1) (bounded)
Space
O(1)
function restoreIpAddresses(s) {
  const result = [];
  function backtrack(i, parts) {
    if (parts.length === 4) {
      if (i === s.length) result.push(parts.join('.'));
      return;
    }
    for (let len = 1; len <= 3 && i + len <= s.length; len++) {
      const seg = s.slice(i, i + len);
      if ((seg[0] === '0' && seg.length > 1) || parseInt(seg, 10) > 255) continue;
      parts.push(seg);
      backtrack(i + len, parts);
      parts.pop();
    }
  }
  backtrack(0, []);
  return result;
}

Tradeoff: Cleaner generalization. Easy to extend to other delimited-format problems.

Snowflake-specific tips

Snowflake interviewers want the validate-segment logic stated up front: 1-3 digits, no leading zero (except '0' itself), value <= 255. Bonus signal: pivot to dotted-identifier parsing — Snowflake's parser splits db.schema.table on dots, with similar validation rules (no leading digits, no empty segments).

Common mistakes

  • Treating '01' as valid (leading zero is disallowed).
  • Allowing 4-digit segments — capped at 3.
  • Stopping backtracking when 4 segments hit but i < s.length — must consume entire input.

Follow-up questions

An interviewer at Snowflake may pivot to one of these next:

  • Generate all valid email-prefix splits.
  • Parse dotted SQL identifiers (db.schema.table.column).
  • Validate IP address (LC 468).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why max 3 digits per segment?

255 is 3 digits. Any 4-digit segment would exceed 255 (1000+).

How does this connect to SQL identifiers?

Snowflake's parser splits db.schema.table on '.' boundaries. The structure validation (3 or 4 segments, valid identifiers) is similar to IP segment validation here.

Practice these live with InterviewChamp.AI

Drill Restore IP Addresses and other Snowflake interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →