Restore IP Addresses

LeetCode 93 | Difficulty: Medium

Medium

Problem Description

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.

- For example, `"0.1.2.201"` and `"192.168.1.1"` are **valid** IP addresses, but `"0.011.255.245"`, `"192.168.1.312"` and `"192.168@1.1"` are **invalid** IP addresses.

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.

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"]

Constraints:

- `1 <= s.length <= 20`

- `s` consists of digits only.

Topics: String, Backtracking

---

Approach

Backtracking

Explore all candidates by building solutions incrementally. At each step, choose an option, explore further, then unchoose (backtrack) to try the next option. Prune branches that can't lead to valid solutions.

When to use

Generate all combinations/permutations, or find solutions that satisfy constraints.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 320 ms)

Metric	Value
Runtime	320 ms
Memory	N/A
Date	2018-02-28

Solution

public class Solution {
public IList<string> RestoreIpAddresses(string s)
{
    List<string> result = new List<string>();
    int len = s.Length;
    if(len>12) return result;
    
    for (int i = 1; i<4 && i < len-2; i++)
    {
        for (int j = i+1; j<i+4 && j < len-1; j++)
        {
            for (int k = j + 1; k < j + 4 && k < len; k++)
            {
                var s1 = Convert.ToInt32(s.Substring(0, i));
                var s2 = Convert.ToInt32(s.Substring(i, j - i));
                var s3 = Convert.ToInt32(s.Substring(j, k - j));
                if (len - k > 0 && len - k <= 3)
                {
                    var s4 = Convert.ToInt32(s.Substring(k, len - k));
                    if (s1 <= 255 && s2 <= 255 && s3 <= 255 & s4 <= 255)
                    {
                        result.Add($"{s1}.{s2}.{s3}.{s4}");
                    }

                }
            }
        }
    }
    return result.Where(x=>x.Length==len+3).ToList();
    
}
}

📜 1 more C# submission(s)

Submission (2018-02-28) — 332 ms, N/A

public class Solution {
public IList<string> RestoreIpAddresses(string s)
{
    List<string> result = new List<string>();
    int len = s.Length;
    for (int i = 1; i<4 && i < len-2; i++)
    {
        for (int j = i+1; j<i+4 && j < len-1; j++)
        {
            for (int k = j + 1; k < j + 4 && k < len; k++)
            {
                var s1 = Convert.ToInt32(s.Substring(0, i));
                var s2 = Convert.ToInt32(s.Substring(i, j - i));
                var s3 = Convert.ToInt32(s.Substring(j, k - j));
                if (len - k > 0 && len - k <= 3)
                {
                    var s4 = Convert.ToInt32(s.Substring(k, len - k));
                    if (s1 <= 255 && s2 <= 255 && s3 <= 255 & s4 <= 255)
                    {
                        result.Add($"{s1}.{s2}.{s3}.{s4}");
                    }

                }
            }
        }
    }
    return result.Where(x=>x.Length==len+3).ToList();
    
}
}

---

Complexity Analysis

Approach	Time	Space
Backtracking	$O(n! or 2^n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Identify pruning conditions early to avoid exploring invalid branches.