Restore IP Addresses

LeetCode Q 93 - Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:
Input: "25525511135" ; Output: ["255.255.11.135", "255.255.111.35"]

Solution : Backtracking

The key point is how to identify a valid IP address.

• Strings whose length greater than 3 or equals to 0 is not valid;
• If the string’s length is longer than 1 and the first letter is ‘0’ then it’s invalid;
• String whose integer representation greater than 255 is invalid.

Code:

private List<String> res;

public List<String> restoreIpAddresses(String s) {
	res = new ArrayList<>();
	if (s == null || s.length() < 4 || s.length() > 12) return res;
	backtrack(s, 0, 0, "");
	return res;
}

private void backtrack (String s, int index, int segments, String curr) {
	if (index == s.length() && segments == 4) {
		res.add(curr.substring(1)); return;
	}
	if (index == s.length() || segments == 4) 
		return;

	for (int i = 1; i <= 3 && index + i <= s.length(); i++) {
		int num = Integer.parseInt(index, index + i);
		if (num == 0 || num > 255 || (num > 10 && s.charAt(index) == '0')) continue;
		backtrack(s, index + i, segments + 1, curr + '.' + s.substring(index, index + i));
	}
}