Backtracking Speedrun ⚡💨

For each of the Speedrun questions, you will be given a backtracking related problem and a corresponding multiple choice question. The multiple choice questions are related to the techniques and template(s) introduced in the backtracking section.

Question 1 of 10

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.

Question

Given a string s and an index start_index, what is the correct implementation for get_edges(start_index) as in the template (i.e. how do we find the potential ip segments that starts with start_index)?

1def get_edges(start_index):
2    segments = []
3    for i in range(start_index, start_index + 3):
4        segements.append(s[start_index:i+1])
5    return segments

1def get_edges(start_index):
2    segments = []
3    for i in range(start_index, start_index + 3):
4        segements.append(s[start_index:i])
5    return segments

1def get_edges(start_index):
2    segments = []
3    for i in range(start_index, start_index + 3):
4        if i > len(s) :
5            segements.append(s[start_index:i])
6    return segments

1def get_edges(start_index):
2    segments = []
3    for i in range(start_index, start_index + 3):
4        if i < len(s) :
5            segements.append(s[start_index:i+1])
6    return segments


Still not clear? Submit the part you don't understand to our editors.