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 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 = "1111" Output: ["1.1.1.1"]
Example 4:
Input: s = "010010" Output: ["0.10.0.10","0.100.1.0"]
Example 5:
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:
0 <= s.length <= 3000s consists of digits only.
The description was taken from https://leetcode.com/problems/restore-ip-addresses/.
#O(1) Time, O(1) Space
#Due to Valid IP Range.
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
if len(s) > 12:
return []
output = []
def in_bounds(byte:str) -> bool:
if int(byte) > 255:
return False
if len(byte) > 1 and byte[0] == "0":
return False
return True
def backtrack(start:int, dots:int, combo:list[str]) -> None:
if dots == 4 and start == len(s):
output.append(".".join(combo))
return
if dots > 4:
return
for i in range(start, min(start+3, len(s))):
byte = s[start:i+1]
if in_bounds(byte):
combo.append(byte)
backtrack(i+1, dots+1, combo)
combo.pop()
backtrack(0, 0, [])
return output
If we are given a problem that requires us to generate each possible combination of something, that is typically an indication that backtracking can be applied.
Backtracking is a Depth-First Search algorithm where we remove a choice whenever the DFS path yoyo returns to the given function. This allows us to circulate elements into each valid position so that we can generate each valid combination.
A general template for backtracking is to set a base case that appends a valid combination for a given DFS path to the output, check if a placement is valid, then make the placement. Once that placement is made, we'd go down a new DFS path with that placement and if that path didn't lead to a solution or it didn't lead to every solution like in this problem, we'd backtrack on the choice to make that placement by removing it from the combination.
This will allow us to get each valid combination of bytes for the given problem.
An IPv4 address is made up of four bytes where the last usable address is reserved.
That means that the maximum number of digits we could have is twelve if we had something similar to 255.255.255.255.
With that being said, if our input string has more than twelve digits then we will return false because we can't make any valid IP addresses using all the digits.
if len(s) > 12:
return []
Otherwise, let's begin by initializing an output array.
output = []
Next, let's go ahead and make a helper function for ourselves to let us know whether a given byte is within bounds of what would be valid.
def in_bounds(byte:str) -> bool:
If the given byte is greater than two hundred fifty-five then that is invalid because as mentioned previously, the maximum number an address byte could be is 2^8 -1 since the last address is unusable.
if int(byte) > 255:
return False
The problem also states that there can't be leading zeros.
If the given byte has a zero as the first index and its size is greater than one, then that means we have a leading zero so this would also be invalid.
if len(byte) > 1 and byte[0] == "0":
return False
Otherwise, this is a valid address byte.
return True
Next, we will create our recursive backtrack function.
The function will take a starting index which we will utilize as the left bound for each byte substring, a number of dots that have been placed within the current DFS path, and an IP address combination that has been created within the current DFS path.
def backtrack(start:int, dots:int, combo:list[str]) -> None:
Let's start by setting our base case.
As mentioned in the beginning, this initial base case will see if we can append a valid combination to the output. That would be determined by if the number of dots we have placed is four, and the starting index has reached the end of the string.
If the number of dots we have placed is four, then that would mean that we have placed four valid IP address bytes.
If the starting index is equal to the length of the string, then that would mean we utilized all of the digits in creating the current combination and didn't derive an IP address like 2.5.5.2 from "25525511135".
If both of those cases are true then we will join the bytes together into a string with a dot delimiter.
Once we have done that, we are finished with this DFS path so we will return from it.
if dots == 4 and start == len(s):
output.append(".".join(combo))
return
Also, this is a slight optimization to prune the recursive tree but if the number of dots we have placed is greater than four, then we have placed too many bytes and nothing down this DFS path will be valid so we will return from here too if that is the case.
if dots > 4:
return
Otherwise, we will take the given start index as the left-bound of the address byte substring and begin expanding with different right bounds to find each valid byte combination.
Ideally, the maximum byte size we could have is three so the end-range would be the starting index plus three since the last index is excluded in Python's ending ranges. However, to avoid going out of bounds of the given input string we can traverse up to the minimum between that end-range and the last index of the string.
for i in range(start, min(start+3, len(s))):
During each iteration, we will slice a given byte between the start index and the current index.
byte = s[start:i+1]
If that byte is in bounds, we will append it to the current IP address combination.
if in_bounds(byte):
combo.append(byte)
From there, we will continue down the DFS path of this combination by recursing the function and incrementing the left bound of the next substring by the next digit after this byte, the number of dots placed by one, and the current combination.
backtrack(i+1, dots+1, combo)
Once the DFS yoyo has returned back up to the function, it will have either lead to a successful combination that was appended to the output or to a bad path that we returned from.
In either case, we will pop the current byte off of the combination and try to expand the right bound of the byte substring by one. This will happen a maximum of three times for any given function call because we chose to only traverse up to the starting index plus three.
This is kind of like us saying, "Okay, we've seen this current byte for this spot, now get out of here so we can give another byte a chance to be here.". This process of popping and appending options is what will allow us to generate each combination in an optimal manner.
combo.pop()
Now that we have our functions built, we just need to make the initial call by passing zero as the starting index, zero as the number of dots placed, and an empty DFS path combination.
backtrack(0, 0, [])
Once our output has been filled, we will return it.
return output