# Restore IP Addresses
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/restore-ip-addresses)
Canonical: https://scaleengineer.com/dsa/problems/restore-ip-addresses
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** String
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Cisco](https://scaleengineer.com/companies/cisco), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Oracle](https://scaleengineer.com/companies/oracle), [Palo Alto Networks](https://scaleengineer.com/companies/palo-alto-networks), [TikTok](https://scaleengineer.com/companies/tiktok), [Visa](https://scaleengineer.com/companies/visa), [Zoho](https://scaleengineer.com/companies/zoho), [Autodesk](https://scaleengineer.com/companies/autodesk), [Arista Networks](https://scaleengineer.com/companies/arista-networks), [StackAdapt](https://scaleengineer.com/companies/stackadapt)
---
## 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.

* 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.

# Approaches
## Recursive Backtracking
This approach uses recursion to explore all possible ways to partition the string into four valid parts. A helper function is defined which tries to build a valid IP address part by part. It explores adding a 1-digit, 2-digit, or 3-digit number as the next part of the IP address, and if the part is valid, it recursively calls itself to find the remaining parts. This method is a classic example of backtracking.
**Time:** O(1) · **Space:** O(1)
**Pros:** It's a standard and elegant way to solve partitioning problems.; The logic is clear and can be easily adapted to similar problems with different constraints.; Pruning can be added to optimize the search, making it more efficient by avoiding impossible paths early.
**Cons:** May have slightly more overhead compared to an iterative solution due to recursive function calls and managing the call stack.; For this specific problem with a fixed number of partitions (4), an iterative approach can be more direct and perform slightly better.
### Explanation
We can model this problem as finding all valid partitions of the string. A recursive backtracking approach is a natural fit for such problems.

We define a recursive function, say `backtrack(s, startIndex, currentPath, result)`:
- `s`: The input string.
- `startIndex`: The index in `s` from where we start looking for the next part.
- `currentPath`: A list of strings representing the parts of the IP address found so far.
- `result`: The list to store the final valid IP addresses.

The base case for the recursion is when we have found 4 parts (`currentPath.size() == 4`). If we have also consumed the entire string (`startIndex == s.length()`), we have found a valid IP address. We join the parts in `currentPath` with dots and add it to the `result`.

In the recursive step, we iterate to choose the next part. The part can have a length of 1, 2, or 3 characters. For each possible length, we extract the substring and validate it. A part is valid if its integer value is between 0 and 255, and it doesn't have a leading zero (unless the part is just "0").

If the part is valid, we add it to our `currentPath` and make a recursive call for the rest of the string. After the recursive call returns, we must "backtrack" by removing the part we just added from `currentPath`. This allows us to explore other possibilities, such as a part of a different length starting from the same position.

```java
class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        if (s.length() < 4 || s.length() > 12) {
            return result;
        }
        backtrack(s, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(String s, int startIndex, List<String> currentPath, List<String> result) {
        if (currentPath.size() == 4) {
            if (startIndex == s.length()) {
                result.add(String.join(".", currentPath));
            }
            return;
        }

        // Pruning: check if remaining characters can form the remaining parts
        int remainingLen = s.length() - startIndex;
        int remainingParts = 4 - currentPath.size();
        if (remainingLen < remainingParts || remainingLen > remainingParts * 3) {
            return;
        }

        for (int i = 1; i <= 3 && startIndex + i <= s.length(); i++) {
            String segment = s.substring(startIndex, startIndex + i);
            if (isValidSegment(segment)) {
                currentPath.add(segment);
                backtrack(s, startIndex + i, currentPath, result);
                currentPath.remove(currentPath.size() - 1); // Backtrack
            }
        }
    }

    private boolean isValidSegment(String segment) {
        if (segment.length() > 1 && segment.startsWith("0")) {
            return false;
        }
        int value = Integer.parseInt(segment);
        return value >= 0 && value <= 255;
    }
}
```
### Algorithm
1. Initialize an empty list `result` to store the valid IP addresses.
2. If the input string `s` has a length less than 4 or greater than 12, it's impossible to form a valid IP, so return the empty `result` list.
3. Create a recursive helper function, let's call it `backtrack(startIndex, path)`.
   - `startIndex` is the current position in the string `s`.
   - `path` is a list of the IP address segments found so far.
4. **Base Case** for the recursion:
   - If the `path` has 4 segments:
     - If `startIndex` is at the end of the string `s`, it means we've successfully partitioned the entire string. Join the segments in `path` with dots and add the resulting IP address to `result`.
     - Return from the function.
5. **Recursive Step**:
   - Loop for segment length `i` from 1 to 3.
   - Check boundary conditions: `startIndex + i` must not exceed the string length.
   - Extract the potential segment: `segment = s.substring(startIndex, startIndex + i)`.
   - Validate the `segment`:
     - It must not have a leading zero unless it is the number 0 itself (e.g., `"01"` is invalid).
     - Its integer value must be between 0 and 255.
   - If the `segment` is valid:
     - Add the `segment` to the current `path`.
     - Make a recursive call: `backtrack(startIndex + i, path)`.
     - **Backtrack**: Remove the `segment` from the `path` to explore other possibilities.
6. Start the process by calling `backtrack(0, new ArrayList<>())`.
7. Return the `result` list.

## Iterative with Nested Loops
This approach avoids recursion and instead uses three nested loops to iterate through all possible positions for the three dots that separate the four parts of an IP address. For each combination of dot positions (which translates to segment lengths), it checks if the resulting four segments form a valid IP address.
**Time:** O(1) · **Space:** O(1)
**Pros:** Very efficient and direct, likely the fastest solution in practice for this problem.; Avoids the overhead of recursion (function call stack), leading to better performance.; The logic is straightforward for this specific problem where the number of partitions is small and fixed.
**Cons:** The code with multiple nested loops can be considered less elegant than a recursive solution.; This approach is less flexible. If the number of parts were variable or the constraints more complex, this approach would become much harder to write and maintain.
### Explanation
Since a valid IP address always has exactly four parts, we can determine all possible partitions by trying all valid lengths for the first three parts. The length of the fourth part is then determined by the remaining characters.

Each of the four parts can have a length of 1, 2, or 3. We can use three nested loops to represent the lengths of the first three parts.
- The outer loop iterates for the length of the first part, `i`, from 1 to 3.
- The second loop iterates for the length of the second part, `j`, from 1 to 3.
- The third loop iterates for the length of the third part, `k`, from 1 to 3.

Inside the innermost loop, we calculate the length of the fourth part, `l = n - (i + j + k)`, where `n` is the total length of the string. If `l` is also between 1 and 3, we have found a potential partition. We then extract the four substrings corresponding to these lengths and validate each one. The validation rules are the same: the value must be in [0, 255] and no illegal leading zeros.

If all four parts are valid, we construct the IP address string and add it to our result list. This method exhaustively checks all `3*3*3 = 27` possible length combinations for the first three parts, making it very efficient for the given constraints.

```java
class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        int n = s.length();

        if (n < 4 || n > 12) {
            return result;
        }

        for (int i = 1; i <= 3; i++) {
            for (int j = 1; j <= 3; j++) {
                for (int k = 1; k <= 3; k++) {
                    if (i + j + k < n && i + j + k >= n - 3) {
                        String s1 = s.substring(0, i);
                        String s2 = s.substring(i, i + j);
                        String s3 = s.substring(i + j, i + j + k);
                        String s4 = s.substring(i + j + k);

                        if (isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)) {
                            result.add(s1 + "." + s2 + "." + s3 + "." + s4);
                        }
                    }
                }
            }
        }
        return result;
    }

    private boolean isValid(String segment) {
        if (segment.length() > 1 && segment.startsWith("0")) {
            return false;
        }
        int value = Integer.parseInt(segment);
        return value <= 255;
    }
}
```
### Algorithm
1. Initialize an empty list `result`.
2. Get the length `n` of the input string `s`. If `n < 4` or `n > 12`, return `result`.
3. Use three nested loops, each iterating from 1 to 3, to represent the lengths `i, j, k` of the first three IP address segments.
4. Inside the loops, calculate the length of the fourth segment: `l = n - (i + j + k)`.
5. If `l` is between 1 and 3 (inclusive), it means we have found a valid partition of the string into four segments of lengths `i, j, k, l`.
   a. Extract the four substrings based on these lengths.
   b. Validate each of the four substrings. A substring is valid if it doesn't have a leading zero (unless it's "0") and its integer value is at most 255.
   c. If all four substrings are valid, combine them with dots to form an IP address string and add it to the `result` list.
6. After the loops complete, return the `result` list.

# Solutions
### CSharp

```csharp
public class Solution {
    private IList < string > ans = new List < string > ();
    private IList < string > t = new List < string > ();
    private int n;
    private string s;
    public IList < string > RestoreIpAddresses(string s) {
        n = s.Length;
        this.s = s;
        dfs(0);
        return ans;
    }
    private void dfs(int i) {
        if (i >= n && t.Count == 4) {
            ans.Add(string.Join(".", t));
            return;
        }
        if (i >= n || t.Count == 4) {
            return;
        }
        int x = 0;
        for (int j = i; j < i + 3 && j < n; ++j) {
            x = x * 10 + (s[j] - '0');
            if (x > 255 || (j > i && s[i] == '0')) {
                break;
            }
            t.Add(x.ToString());
            dfs(j + 1);
            t.RemoveAt(t.Count - 1);
        }
    }
}
```

### Java

```java
class Solution { private int n ; private String s ; private List < String > ans = new ArrayList <>(); private List < String > t = new ArrayList <>(); public List < String > restoreIpAddresses ( String s ) { n = s . length (); this . s = s ; dfs ( 0 ); return ans ; } private void dfs ( int i ) { if ( i >= n && t . size () == 4 ) { ans . add ( String . join ( "." , t )); return ; } if ( i >= n || t . size () >= 4 ) { return ; } int x = 0 ; for ( int j = i ; j < Math . min ( i + 3 , n ); ++ j ) { x = x * 10 + s . charAt ( j ) - '0' ; if ( x > 255 || ( s . charAt ( i ) == '0' && i != j )) { break ; } t . add ( s . substring ( i , j + 1 )); dfs ( j + 1 ); t . remove ( t . size () - 1 ); } } } ////// import java.util.ArrayList ; import java.util.List ; public class Restore_IP_Addresses { public static void main ( String [] args ) { // @note:@memorize: test substring boundary String a = "abc" ; // a = a.substring(0, 4); // String index out of range: 4 a = a . substring ( 0 , 3 ); // ok System . out . println ( a ); Restore_IP_Addresses out = new Restore_IP_Addresses (); Solution s = out . new Solution (); for ( String each: ( s . restoreIpAddresses ( "25525511135" ))) { System . out . println ( each ); } } List < String > list = new ArrayList <>(); public class Solution { public List < String > restoreIpAddresses ( String s ) { if ( s . length () < 4 || s . length () > 12 || ! s . matches ( "\\d+" )) { return list ; } restore ( s , "" , 0 ); return list ; } // seg: segment, in total 4 private void restore ( String s , String result , int seg ) { if ( seg == 4 ) { if ( s . length () == 0 ) { // remove last "." result = result . substring ( 0 , result . length () - 1 ); list . add ( result ); } return ; } // for (int i = 0; i < 3; i++) { // @note: out of boundary for ( int i = 0 ; i < 3 && i < s . length (); i ++) { String thisSeg = s . substring ( 0 , i + 1 ); if ( isValid ( thisSeg )) { restore ( s . substring ( i + 1 ), result + thisSeg + "." , seg + 1 ); } } } private boolean isValid ( String s ) { // can NOT be: 10.01.1.1 if ( s . length () > 1 && s . startsWith ( "0" )) { return false ; } int n = Integer . valueOf ( s ); if ( n > 255 ) { return false ; } return true ; } } }
```

### CPP

```cpp
class Solution {
public:
  vector<string> restoreIpAddresses(string s) {
    int n = s.size();
    vector<string> ans;
    vector<string> t;
    function<void(int)> dfs = [&](int i) {
      if (i >= n && t.size() == 4) {
        ans.push_back(t[0] + "." + t[1] + "." + t[2] + "." + t[3]);
        return;
      }
      if (i >= n || t.size() >= 4) {
        return;
      }
      int x = 0;
      for (int j = i; j < min(n, i + 3); ++j) {
        x = x * 10 + s[j] - '0';
        if (x > 255 || (j > i && s[i] == '0')) {
          break;
        }
        t.push_back(s.substr(i, j - i + 1));
        dfs(j + 1);
        t.pop_back();
      }
    };
    dfs(0);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]: def check(i: int, j: int) -> int: if s[i] == "0" and i != j: return False return 0 <= int(s[i: j + 1]) <= 255 def dfs(i: int): if i >= n and len(t) == 4: ans . append("." . join(t)) return if i >= n or len(t) >= 4: return for j in range(i, min(i + 3, n)): if check(i, j): t . append(s[i: j + 1]) dfs(j + 1) t . pop() n = len(s) ans = [] t = [] dfs(0) return ans

```