Restore Ip Addresses - Leetcode Solution

Problem Statement:

Given a string s containing only digits, return all possible valid IP addresses that can be obtained from s. You can return them in any order.

A valid IP address consists of exactly four integers, each integer is between 0 and 255, separated by single dots and cannot have leading zeros. For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses and "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.

Example:

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

Solution:

This problem can be solved by using a combination of Depth First Search (DFS) and Backtracking algorithms. The key idea behind the solution of this problem is to find all possible combinations of valid IP addresses by dividing a given string into 4 parts, applying the constraints of IP addresses and checking if they are valid or not.

We can start by using a recursive function, where we fix the total number of parts that an IP address can have. In this case, an IP Address has 4 parts, each separated by a dot. Therefore, we will fix the number of dots (or separators) to 3 for the given string. A DFS approach can be used to traverse through all the possible combinations of partitions and remove the invalid IP Addresses using the given set of conditions.

Let's consider the example "25525511135". The algorithm will start by placing the first dot at a valid position, which can be any index from 1 to 3 (inclusive). We can use a loop to iterate through all the possible positions at which we can place the first dot. We will continue this process for all the three dots, which will give us all possible combinations of partitions.

At each recursive call of the DFS function, we keep track of the current partition number, the list of partitions so far, and the current starting index. The recursive function will call itself for each valid partition, and if the partition list has 4 elements and the entire string has been processed, we know that we have found a valid IP address.

However, we also need to check that the partitions meet the constraints of a valid IP address. The following cases will be invalid:

• If a partition has more than one digit and starts with a '0' (e.g., "01")
• If a partition has a value greater than 255
• If the current partition list is not of length 4 and the entire string has been processed.

If any of the conditions above are met, we will backtrack and continue with the next partition.

Here is the implementation in Python:

class Solution: def restoreIpAddresses(self, s: str) -> List[str]: res = [] self.dfs(s, 0, [], res) return res

def dfs(self, s: str, start: int, partitions: List[str], res: List[str]):
    # If all 4 partitions found and the entire string has been processed
    if len(partitions) == 4 and start == len(s):
        res.append('.'.join(partitions))
        return
    
    # If all partitions have been found, but not the entire string
    elif len(partitions) == 4:
        return
    
    # Iterate through positions to place dots
    for i in range(start, min(len(s), start+3)):
        partition = s[start:i+1]
        
        # Check for invalid partitions
        if (len(partition) > 1 and partition.startswith('0')) or int(partition) > 255:
            continue
        
        # Recursively call DFS to find next partition
        self.dfs(s, i+1, partitions+[partition], res)

1