Sponsored
Sponsored
This approach utilizes backtracking to explore all possible placements of the three dots in the string. We attempt to generate valid IP segments recursively, ensuring each generated segment maintains the restrictions of a valid IP address. By backtracking, we can explore each possible path of placing dots and ensure we cover all potential valid configurations.
Time Complexity: O(2^n), due to the exponential number of ways to split the string, though practical time for small strings like ours is quite feasible.
Space Complexity: O(n), for the recursion stack and to store the IP parts temporarily.
1def restore_ip_addresses(s):
2 def backtrack(start, parts):
3 if len(parts) == 4:
4 if start == len(s):
5 result.append(".".join(parts))
6 return
7
8 for i in range(1, 4):
9 if start + i > len(s):
10 break
11 part = s[start:start+i]
12 if (len(part) > 1 and part[0] == '0') or (int(part) > 255):
13 continue
14 backtrack(start + i, parts + [part])
15
16 result = []
17 backtrack(0, [])
18 return result
19
20# Example usage:
21# restore_ip_addresses("25525511135")This Python function defines a helper function backtrack, which takes the current starting index and a list of constructed IP parts. We recursively attempt to build valid segments, ensuring they adhere to IP rules (no leading zeros, within [0, 255] range), and append valid results to the result list. We explore segments of lengths 1 to 3, backtracking appropriately.
In this approach, we iterate through potential splits for the three dots required to form four IP sections. For each potential set of positions, we validate and construct the IP address. Although typically not as elegant as the recursive backtracking solution, it's systematic and allows us to explore and validate possible IP addresses through combinatorial checks.
Time Complexity: O(n^3), given the triple nested loop for positions.
Space Complexity: O(1), ignoring the output list space.
1#include <iostream>
2#include <vector>
3#include <string>
4using namespace std;
5
vector<string> restoreIpAddresses(string s) {
vector<string> result;
int n = s.size();
for (int i = 1; i < 4 && i < n - 2; ++i) {
for (int j = i + 1; j < i + 4 && j < n - 1; ++j) {
for (int k = j + 1; k < j + 4 && k < n; ++k) {
string s1 = s.substr(0, i);
string s2 = s.substr(i, j - i);
string s3 = s.substr(j, k - j);
string s4 = s.substr(k);
if (isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)) {
result.push_back(s1 + "." + s2 + "." + s3 + "." + s4);
}
}
}
}
return result;
}
bool isValid(const string &s) {
if (s.size() > 3 || (s[0] == '0' && s.size() > 1) || stoi(s) > 255) {
return false;
}
return true;
}
int main() {
vector<string> result = restoreIpAddresses("25525511135");
for (const string &ip : result) {
cout << ip << endl;
}
return 0;
}This C++ solution uses a three-level nested loop to estimate possible positions of dots for dividing the string into four parts. For each configuration, it calls a helper function isValid to check if each part is a valid IP section (not exceeding 255 and no leading zero unless the part is zero itself).