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 at start_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