Generate all valid IP addresses from a string

Medium

Problem

Given a string of digits, return every valid IPv4 address you can form by inserting three dots. Each of the four parts must be between 0 and 255 and must not have a leading zero (so "0" is allowed but "01" is not).

Example 1

Input:  "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

Also asked as: Program to generate all possible valid IP addresses from given string

Test cases

Case 1

Input:    "25525511135"
Expected (any order): ["255.255.11.135","255.255.111.35"]

Case 2

Input:    "101023"
Expected (any order): ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

Case 3

Input:    "0000"
Expected (any order): ["0.0.0.0"]

Case 4

Input:    "123"
Expected (any order): []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Backtracking with 4 segments

Time O(1) — at most 3⁴ splitsSpace O(1)

Place 3 dots. Each of the 4 parts is 1–3 digits, ≤ 255, and has no leading zero (unless it is "0").

function restoreIps(s) {
const res = [];
const valid = (seg) => seg.length >= 1 && seg.length <= 3 &&
(seg === '0' || (seg[0] !== '0' && +seg <= 255));
const bt = (start, parts) => {
if (parts.length === 4) { if (start === s.length) res.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)) bt(start + len, [...parts, seg]);
}
};
bt(0, []);
return res;
}