Skip to main content

67. Restore IP Addresses

mediumAsked at Plaid

Generate all valid IP addresses from a digit string. Plaid asks this as a backtracking warm-up — the same shape they use when parsing variable-length transaction codes split across delimiters.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • LeetCode Discuss (2026)— Plaid SWE II OA backtracking.
  • Glassdoor (2025)— Plaid platform-team screen.

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.

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. Enumerate all 3-dot placements

Try every (i, j, k) for dot positions; validate each octet.

Time
O(n^3)
Space
O(1) extra
// Triple nested loop. Works for short s.

Tradeoff: Workable. The string is short (n <= 20), so the cubic factor is bounded.

2. Backtracking with octet validation

Recurse with current position and octet count. At each step, try 1-, 2-, 3-digit octets, validating each.

Time
O(3^4)
Space
O(1) extra
function restoreIpAddresses(s) {
  const out = [];
  function valid(seg) {
    if (seg.length === 0 || seg.length > 3) return false;
    if (seg.length > 1 && seg[0] === '0') return false;
    return parseInt(seg, 10) <= 255;
  }
  function bt(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.slice(start, start + len);
      if (valid(seg)) {
        parts.push(seg);
        bt(start + len, parts);
        parts.pop();
      }
    }
  }
  bt(0, []);
  return out;
}

Tradeoff: Bounded by 3^4 = 81 branches. The 'leading zero unless the segment is exactly '0'' rule is the only octet subtlety.

Plaid-specific tips

Plaid grades this on the leading-zero rule because that's where most candidates slip. Bonus signal: enumerate all three octet rules out loud before coding: 1-3 digits, no leading zero unless segment is '0', value 0-255. Connect to parsing routing numbers split into variable-length code segments.

Common mistakes

  • Allowing '01' or '001' as valid octets.
  • Forgetting the value <= 255 check.
  • Returning when parts.length === 4 without checking start === s.length — produces incomplete IPs.

Follow-up questions

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

  • Restore valid IPv6 addresses.
  • Find the lexicographically smallest valid IP.
  • Streaming IP-restoration from a continuous digit feed.

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 no leading zeros?

The spec disallows them — '01' is not a valid octet. Only '0' itself is allowed as a zero.

Why 3-deep recursion, not 4?

Each level of recursion picks one octet. After 4 picks we check we've consumed all digits — if not, this partition isn't valid.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →