Dare2Solve
The restoreIpAddresses
function generates all possible valid IP addresses from a given string of digits. An IP address consists of four segments separated by periods, where each segment is a number between 0 and 255. The input string does not contain any periods, and the goal is to insert them in such a way that all resulting IP addresses are valid.
The problem requires us to split the string into four valid segments, ensuring that each segment is within the range of 0 to 255. Additionally, segments cannot have leading zeros unless they are exactly "0". This constraint guides the formation of potential IP addresses as we explore all valid ways to insert the periods.
Depth-First Search (DFS):
Base Cases:
Backtracking:
Joining Segments:
The time complexity is (O(3^4)) or (O(81)), as we consider up to 3 characters for each of the 4 segments. However, the actual complexity is lower due to constraints (like leading zeros and the maximum value of 255) which limit the number of valid segments.
The space complexity is (O(n)), where (n) is the length of the input string. This accounts for the space used by the recursion stack and the storage of the result list.
class Solution {
public:
std::vector<std::string> restoreIpAddresses(std::string s) {
std::vector<std::string> res;
std::vector<std::string> arr;
dfs(s, arr, 0, res);
return res;
}
private:
void dfs(const std::string& s, std::vector<std::string>& arr, int start, std::vector<std::string>& res) {
if (start == s.length() && arr.size() == 4) {
res.push_back(join(arr, '.'));
return;
}
if (start == s.length() || arr.size() == 4) {
return;
}
std::string num = "";
for (int i = start; i < s.length() && std::stoi(num + s[i]) <= 255; i++) {
if (s[start] == '0' && i != start) break;
num += s[i];
arr.push_back(num);
dfs(s, arr, i + 1, res);
arr.pop_back();
}
}
std::string join(const std::vector<std::string>& vec, char delimiter) {
std::string result;
for (int i = 0; i < vec.size(); i++) {
if (i > 0) {
result += delimiter;
}
result += vec[i];
}
return result;
}
};
class Solution:
def restoreIpAddresses(self, s: str):
res = []
arr = []
def dfs(s, arr, start):
if start == len(s) and len(arr) == 4:
res.append('.'.join(arr))
return
if start == len(s) or len(arr) == 4:
return
num = ''
for i in range(start, len(s)):
if int(num + s[i]) > 255:
break
if s[start] == '0' and i != start:
break
num += s[i]
arr.append(num)
dfs(s, arr, i + 1)
arr.pop()
dfs(s, arr, 0)
return res
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<>();
List<String> arr = new ArrayList<>();
dfs(s, arr, 0, res);
return res;
}
private void dfs(String s, List<String> arr, int start, List<String> res) {
if (start == s.length() && arr.size() == 4) {
res.add(String.join(".", arr));
return;
}
if (start == s.length() || arr.size() == 4) {
return;
}
String num = "";
for (int i = start; i < s.length() && Integer.parseInt(num + s.charAt(i)) <= 255; i++) {
if (s.charAt(start) == '0' && i != start) break;
num += s.charAt(i);
arr.add(num);
dfs(s, arr, i + 1, res);
arr.remove(arr.size() - 1);
}
}
}
var restoreIpAddresses = function(s) {
const res = [], arr = [];
function dfs(s, arr, start) {
if(start === s.length && arr.length === 4) {
res.push(arr.join('.'));
return;
}
if(start === s.length || arr.length === 4) {
return;
}
let num = '';
for(let i = start; i < s.length && num + s[i] <= 255; i++) {
if(s[start] === '0' && i != start) break;
num += s[i];
console.log(num);
arr.push(num);
dfs(s, arr, i + 1);
arr.pop();
}
}
dfs(s, arr, 0);
return res;
};