JAVA

all possible valid IP addresses leetcode

/*
	This implementation demonstrates how 
	to generate all valid IP addresses
	based on a string that is made up of 
	digits only.

	Time complexity: O(1) 
	Space complexity: O(1)
*/
import java.util.List;
import java.util.ArrayList;

public class ValidIPAddresses {
	public static void main(String[] args) {
		String s = "25525511135";
		// Below prints: [255.255.11.135, 255.255.111.35]
		System.out.println(generateIpAddresses(s));
	}

	private static List<String> generateIpAddresses(String s) {
		List<String> allPossibleIPs = new ArrayList<>();
		int length = s.length();
		for (int idx1 = 1; idx1 < Math.min(length, 4); idx1++) {
			String[] currentIPParts = new String[] { "", "", "", "" };
			currentIPParts[0] = s.substring(0, idx1);
			if (!isValid(currentIPParts[0])) {
				continue;
			}

			for (int idx2 = idx1 + 1; idx2 < idx1 + Math.min(length - idx1, 4); idx2++) {
				currentIPParts[1] = s.substring(idx1, idx2);
				if (!isValid(currentIPParts[1])) {
					continue;
				}

				for (int idx3 = idx2 + 1; idx3 < idx2 + Math.min(length - idx2, 4); idx3++) {
					currentIPParts[2] = s.substring(idx2, idx3);
					currentIPParts[3] = s.substring(idx3);
					if (isValid(currentIPParts[2]) && isValid(currentIPParts[3])) {
						allPossibleIPs.add(String.join(".", currentIPParts));
					}

				}
			}

		}

		return allPossibleIPs;
	}

	private static boolean isValid(String part) {
		if (part.length() > 3) {
			return false;
		}
		int partAsInt = Integer.parseInt(part);
		// Any part greater than 255 is not valid
		if (partAsInt > 255) {
			return false;
		}
		// Account for leading 0s
		return part.length() == Integer.toString(partAsInt).length();
	}

}