Skip to main content

70. Restore IP Addresses

mediumAsked at Ola

Generate all valid IP addresses that can be formed from a string of digits.

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

Problem

Given a string s containing only digits, return all possible valid IP addresses that can be obtained by inserting dots into s. You cannot 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"]

Approaches

1. Triple loop

Try every triple of dot positions and validate.

Time
O(n^3)
Space
O(1)
// 3 nested loops over split points, validate each octet

Tradeoff:

2. DFS with 4-segment cap

Recurse with current segment count and remaining string; prune by length and validate each segment.

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

Tradeoff:

Ola-specific tips

Ola asks this to verify clean octet validation; tie it to parsing back-of-envelope IPv4 strings from a driver-device telemetry payload.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →