LeetCode Restore IP Addresses Solution
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 "[email protected]"
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.
Problem Link: https://leetcode.com/problems/restore-ip-addresses/
Solution
We want to apply our template backtracking1 to this problem. To fill in the logic:
is_leaf
:start_index == len(s) and
len(path) == 4`, when all of the digits are used and there are exactly 4 segments.get_edges
: the edges are the potential segments (of size 1-3) that starts atstart_index
.is_valid
: is the edge (integer) between 0 to 255? and does it not have a leading zero?
Implementation
1def restoreIpAddresses(self, s: str) -> List[str]:
2 def to_ip_address(path):
3 address = path[0]
4 for i in range(1, 4): address += "." + path[i]
5 return address
6
7 def get_edges(start_index):
8 segments = []
9 for i in range(start_index, start_index + 3):
10 if i < len(s) : # if not out of bound
11 segments.append(s[start_index:i+1]) # up to and including s[i]
12 return segments
13
14 def is_valid(num):
15 if num == "0": return True
16 elif num[0] == "0": return False # leading zero
17 elif int(num) > 255: return False # out of range
18 else: return True
19
20 def dfs(start_index, path):
21 if len(path) > 4: return
22 if start_index == len(s): # if all digits are used
23 if len(path) == 4: # and there are exactly four segments
24 ans.append(to_ip_address(path)) # add address to the result
25 return
26 for edge in get_edges(start_index):
27 if is_valid(edge):
28 path.append(edge)
29 dfs(start_index + len(edge), path)
30 path.pop()
31 ans = []
32 print(s[0:len(s)+1])
33 dfs(0, [])
34 return ans