Restore IP Addresses Editorial

Practice Problem Link: Restore IP Addresses

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a digit string, return all possible IP Addresses that can be formed from the string. A valid IP Address contains four integers each in the range of [0, 255]. The four numbers are separated by a '.'. The integers do not have any leading zeros unless the number is itself 0.

Approach

We use a backtracking-based approach to solve this problem. We will try to put 3 ‘.’ in all the possible positions and check if the numbers formed by their partitions are valid or not. If at any point, at any initial partitions only we find that the string will become invalid, we can backtrack at that step only, making the average-case complexity much better. If a valid string is found, we store it in our list and move on with our search for other strings.

Analysis

• Time Complexity: O(n * number of possible strings)
• Space Complexity: O(n * number of possible strings)

Implementation

C++

vector<string> address;
vector<int> numberList;
void solve(string c, int start, int n){
		if(start == n) {
		int flag = 1;
		if(numberList.size() != 4) {
			return;
		}
		for(int i: numberList) {
			if(i >= 0 && i <= 255) {
				continue;
			}
			flag = 0;
			break;
		}

		if(flag == 1){
			string auxiliary = "";
			for(int i: numberList) {
				auxiliary += (to_string(i) + ".");
			}
			if(auxiliary.length() == n + 4) {
				address.push_back(auxiliary.substr(0, auxiliary.length()-1));
			}
		}
		return;
	}

	int num = 0;
	for(int i = start; i < n; i++) {
		num = num * 10 + (c[i] - '0');
		numberList.push_back(num);
		solve(c, i + 1, n);
		numberList.pop_back();
	}
}
vector<string> restoreIPAddresses(string s) {
    address.clear();
	numberList.clear();
	solve(s, 0, s.length());
	return address;
}

Java

class Solution {
	List<String> address;
	ArrayList<Integer> numberList;
	List<String> restoreIPAddresses(String s) {
		address = new ArrayList<>();
		numberList = new ArrayList<>();
		solve(s.toCharArray(), 0, s.length());
		return address;
	}
	void solve(char c[], int start, int n){
		if(start == n) {
			int flag = 1;
			if(numberList.size() != 4) {
				return;
			}
			for(int i: numberList) {
				if(i >= 0 && i <= 255) {
					continue;
				}
				flag = 0;
				break;
			}
			
			if(flag == 1){
				String auxiliary = "";
				for(int i: numberList) {
					auxiliary += i + ".";
				}
				if(auxiliary.length() == n + 4)
					address.add(auxiliary.substring(0, auxiliary.length() - 1));
			}
			return;
		}
		
		int num = 0;
		for(int i = start; i < n; i++) {
			num = num * 10 + (c[i] - '0');
			numberList.add(num);
			solve(c, i + 1, n);
			numberList.remove(numberList.size() - 1);
		}
	}
}