Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in C#

Solution: Restore IP Addresses

Explore the backtracking approach to restore valid IP addresses from a numeric string. This lesson guides you through constructing IP segments, validating each part, and recursively placing dots to generate all possible valid combinations. You will understand how to optimize dot placement and ensure each segment conforms to IP addressing rules, enabling you to solve similar constraint satisfaction problems efficiently.

We'll cover the following...

Statement

A valid IP address consists of four numeric segments separated by single dots. Each segment must be an integer between 0 and 255 (inclusive), and leading zeros are not allowed unless the segment is exactly ‘0.”

For instance, “10.0.1.25” and “172.16.0.5” are valid IP addresses, while “01.200.100.3,” “256.100.50.25,” and “172.16.0.500” are invalid.

Given a string s made up of digits only, return all possible valid IP addresses that can be created by inserting exactly three dots into the string. You cannot rearrange or delete any digits. The resulting list of valid IP addresses can be returned in any order.

Constraints:

  • The input string s consists of digits only.

  • 4≤4 \leq s.length ≤12\leq 12

Naive approach

The naive approach would be to check all possible positions of the dots. Because an IP address requires inserting three dots, and if the input string contains 1212 digits, then there are 1111 possible positions between the digits where a dot can be placed. So, we initially have 1111 choices for the first dot, then ...