Skip to main content

66. Restore IP Addresses

mediumAsked at Vercel

Given a string of digits, return all valid IP addresses that can be formed. Vercel asks this for the bounded-backtracking pattern with multiple validation rules — exactly the shape of validating their edge node IP allowlists.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel routing-team onsite; explicit IP validation.
  • Blind (2026-Q1)— Listed in Vercel screen pool.

Problem

Given a string s containing only digits, return all possible valid IP addresses that can be obtained from s. You can return them in any order. A valid IP address consists of exactly four integers, each between 0 and 255, separated by single dots. No leading zeros allowed (except '0' itself).

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 loop over three dots

Try every position for dot1, dot2, dot3; validate each of the 4 segments.

Time
O(1) (bounded by 3^3 splits)
Space
O(1)
function restoreIpAddresses(s) {
  const out = [];
  const ok = (seg) => seg.length > 0 && seg.length <= 3 && (seg === '0' || (seg[0] !== '0' && +seg <= 255));
  for (let i = 1; i < s.length - 2 && i <= 3; i++) {
    for (let j = i + 1; j < s.length - 1 && j - i <= 3; j++) {
      for (let k = j + 1; k < s.length && k - j <= 3; k++) {
        const a = s.slice(0, i), b = s.slice(i, j), c = s.slice(j, k), d = s.slice(k);
        if (ok(a) && ok(b) && ok(c) && ok(d)) out.push(`${a}.${b}.${c}.${d}`);
      }
    }
  }
  return out;
}

Tradeoff: Clean for fixed-arity (4 segments). For variable arity, prefer backtracking.

2. Backtracking with depth limit

DFS: place dots; track segments placed. Prune when segment > 3 chars or invalid.

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

Tradeoff: Generalizes to k segments. Bounded by 3^4 segment trials in the worst case.

Vercel-specific tips

Vercel grades the validation rules. Bonus signal: explicitly listing the four rules (1-3 chars, no leading zero except '0' itself, value 0-255, exactly 4 segments using all characters). Articulate before coding to avoid missing one.

Common mistakes

  • Allowing '00' or '012' — leading zeros are invalid unless the segment is just '0'.
  • Forgetting to consume the entire string — the last segment must end at s.length.
  • Allowing segment > 3 chars — the digits 256+ are out of range, but more strictly, no segment can be longer than 3 digits.

Follow-up questions

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

  • Restore IPv6 addresses — more complex.
  • Validate one IP address (LC 468).
  • Generate the lexicographically smallest valid IP.

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 exclude '01' but allow '0'?

IP segments don't have leading zeros — '01' would be ambiguous (octal interpretation in some parsers). '0' alone is valid; '00' and '01' are not.

Maximum number of valid IPs for a given input?

Bounded by 3^3 = 27 (three dot positions, each with 3 length choices). Most inputs produce far fewer due to validation rules.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →