Problem Statement: Restore IP Addresses
Given a string s containing only digits, restore it by returning all possible valid IP address combinations.
A valid IP address consists of exactly four integers separated by periods (.), where each integer is between 0 and 255 (inclusive), and no integer has leading zeros unless it is “0”.
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 = "1111"
Output:
["1.1.1.1"]
Approach
To solve this problem, we can use backtracking or depth-first search (DFS) to explore all possible valid IP address combinations. Each valid IP address consists of four parts, each part being a number between 0 and 255, and each part must not have leading zeros unless it is exactly “0”.
Key Constraints:
- The string must be split into exactly four segments.
- Each segment should be a number between 0 and 255.
- The segment should not contain leading zeros unless it is exactly “0”.
- The total length of the string
sshould be between 4 and 12 to form a valid IP address (since each segment must contain at least one digit).
Plan:
- Backtracking:
- Split the string into 4 parts using backtracking.
- For each part, check if the part is a valid number (i.e., in the range 0-255 and does not have leading zeros unless it is “0”).
- Base Case: Once we have four valid parts, join them using dots (
.) and add them to the result. - Recursive Case: Try different segment lengths (1 to 3 characters) for each part and recursively explore the remaining string.
Time Complexity:
- Time Complexity: O(n^3), where
nis the length of the string. We are exploring all combinations of three split points and checking if each part is valid. - Space Complexity: O(n), where
nis the length of the string. We store the current result in the backtracking process.
Code Implementation
C Code
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void backtrack(char *s, int start, int part, char *current, char **result, int *resultCount) {
if (part == 4) {
if (start == strlen(s)) {
result[*resultCount] = strdup(current);
(*resultCount)++;
}
return;
}
for (int len = 1; len <= 3; len++) {
if (start + len > strlen(s)) break;
char temp[len + 1];
strncpy(temp, s + start, len);
temp[len] = '\0';
// Check validity of the segment
if ((len == 1) || (temp[0] != '0' && atoi(temp) <= 255)) {
char nextCurrent[100];
snprintf(nextCurrent, sizeof(nextCurrent), "%s%s%s", current, (part == 0 ? "" : "."), temp);
backtrack(s, start + len, part + 1, nextCurrent, result, resultCount);
}
}
}
char** restoreIpAddresses(char* s, int* returnSize) {
char **result = (char **)malloc(100 * sizeof(char*));
*returnSize = 0;
if (strlen(s) < 4 || strlen(s) > 12) return result;
backtrack(s, 0, 0, "", result, returnSize);
return result;
}
int main() {
char s[] = "25525511135";
int returnSize = 0;
char **result = restoreIpAddresses(s, &returnSize);
printf("Possible IPs:\n");
for (int i = 0; i < returnSize; i++) {
printf("%s\n", result[i]);
free(result[i]);
}
free(result);
return 0;
}
C++ Code
#include <iostream>
#include <vector>
#include <string>
using namespace std;
void backtrack(string& s, int start, int part, string current, vector<string>& result) {
if (part == 4) {
if (start == s.size()) {
result.push_back(current);
}
return;
}
for (int len = 1; len <= 3; len++) {
if (start + len > s.size()) break;
string temp = s.substr(start, len);
// Check validity of the segment
if ((len == 1) || (temp[0] != '0' && stoi(temp) <= 255)) {
backtrack(s, start + len, part + 1, current + (part == 0 ? "" : ".") + temp, result);
}
}
}
vector<string> restoreIpAddresses(string s) {
vector<string> result;
if (s.size() < 4 || s.size() > 12) return result;
backtrack(s, 0, 0, "", result);
return result;
}
int main() {
string s = "25525511135";
vector<string> result = restoreIpAddresses(s);
cout << "Possible IPs:" << endl;
for (const string& ip : result) {
cout << ip << endl;
}
return 0;
}
Java Code
import java.util.ArrayList;
import java.util.List;
public class RestoreIPAddresses {
private void backtrack(String s, int start, int part, String current, List<String> result) {
if (part == 4) {
if (start == s.length()) {
result.add(current);
}
return;
}
for (int len = 1; len <= 3; len++) {
if (start + len > s.length()) break;
String temp = s.substring(start, start + len);
// Check validity of the segment
if ((len == 1) || (temp.charAt(0) != '0' && Integer.parseInt(temp) <= 255)) {
backtrack(s, start + len, part + 1, current + (part == 0 ? "" : ".") + temp, result);
}
}
}
public List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<>();
if (s.length() < 4 || s.length() > 12) return result;
backtrack(s, 0, 0, "", result);
return result;
}
public static void main(String[] args) {
RestoreIPAddresses solution = new RestoreIPAddresses();
String s = "25525511135";
List<String> result = solution.restoreIpAddresses(s);
System.out.println("Possible IPs:");
for (String ip : result) {
System.out.println(ip);
}
}
}
Python Code
def restoreIpAddresses(s):
result = []
def backtrack(start, part, current):
if part == 4:
if start == len(s):
result.append(current)
return
for length in range(1, 4):
if start + length > len(s):
break
temp = s[start:start + length]
# Check validity of the segment
if (length == 1) or (temp[0] != '0' and int(temp) <= 255):
backtrack(start + length, part + 1, current + ('.' if part > 0 else '') + temp)
if len(s) < 4 or len(s) > 12:
return result
backtrack(0, 0, "")
return result
# Example usage
s = "25525511135"
result = restoreIpAddresses(s)
print("Possible IPs:")
for ip in result:
print(ip)
C# Code
using System;
using System.Collections.Generic;
public class RestoreIPAddresses
{
private void Backtrack(string s, int start, int part, string current, List<string> result)
{
if (part == 4)
{
if (start == s.Length)
{
result.Add(current);
}
return;
}
for (int len = 1; len <= 3; len++)
{
if (start + len > s.Length) break;
string temp = s.Substring(start, len);
// Check validity of the segment
if (len == 1 || (temp[0] != '0' && int.Parse(temp) <= 255))
{
Backtrack(s, start + len, part + 1, current + (part == 0 ? "" : ".") + temp, result);
}
}
}
public List<string> RestoreIpAddresses(string s)
{
List<string> result = new List<string>();
if (s.Length < 4 || s.Length > 12) return result;
Backtrack(s, 0, 0, "", result);
return result;
}
public static void Main()
{
string s = "25525511135";
RestoreIPAddresses solution = new RestoreIPAddresses();
var result = solution.RestoreIpAddresses(s);
Console.WriteLine("Possible IPs:");
foreach (var ip in result)
{
Console.WriteLine(ip);
}
}
}
JavaScript Code
const restoreIpAddresses = (s) => {
const result = [];
const backtrack = (start, part, current) => {
if (part === 4) {
if (start === s.length) {
result.push(current);
}
return;
}
for (let len = 1; len <= 3; len++) {
if (start + len > s.length) break;
const temp = s.slice(start, start + len);
// Check validity of the segment
if (len === 1 || (temp[0] !== '0' && parseInt(temp) <= 255)) {
backtrack(start + len, part + 1, current + (part === 0 ? "" : ".") + temp);
}
}
};
if (s.length < 4 || s.length > 12) return result;
backtrack(0, 0, "");
return result;
};
// Example usage
const s = "25525511135";
const result = restoreIpAddresses(s);
console.log("Possible IPs:");
result.forEach(ip => console.log(ip));
Explanation:
- Backtracking: We recursively explore all possible segments by iterating over 1 to 3 characters and checking their validity.
- Validity Check: Each segment must be a number between 0 and 255 and should not contain leading zeros unless it is “0”.
- Base Case: If we have exactly 4 valid parts and the entire string has been consumed, we add the current combination to the result.
Time and Space Complexity:
- Time Complexity: O(n^3), where
nis the length of the input strings. We generate all combinations of splits and for each split check if the segments are valid. - Space Complexity: O(n), for storing intermediate results during backtracking.