93. Restore IP Addresses

Problem Statement

Pattern:

---

Solution

List<String> res;
 
public void dp (String s, int n, int slot, int slotSize, int[] restored) {
	if (slotSize > 3 || n != -1 && slot < 0 || n == -1 && slot >-1) return;
	if (n == -1 && slot == -1) {
		StringBuilder sb = new StringBuilder();
		for(int ip : restored) sb.append(ip).append(".");
		sb.setLength(sb.length()-1);
		res.add(sb.toString());
		return;        
	}
	
	// add slot
	String substr = s.substring(n, n+slotSize);
	int val = Integer.parseInt(substr);
	if(val <= 255 && !(substr.length() > 1 && substr.charAt(0)=='0')) {
		restored[slot] = val;
		dp(s, n-1, slot-1, 1, restored);
	}
	// continue slot
	dp(s, n-1, slot, slotSize+1, restored);
	
}
 
public List<String> restoreIpAddresses(String s) {
	res = new ArrayList<>();
	dp(s, s.length()-1, 3, 1, new int[4]);
	return res;
}

TC : $O(n^2)$ SC : $O(n^2)$

Notes

• pretty self explanatory, once you look at the code

Caching not working. ask @Gaurav to explain

List<String> res;
boolean cache[][][];
 
public void dp (String s, int n, int slot, int slotSize, int[] restored) {
	if (slotSize > 3 || n != -1 && slot < 0 || n == -1 && slot >-1) return;
	if (n == -1 && slot == -1) {
		StringBuilder sb = new StringBuilder();
		for(int ip : restored) sb.append(ip).append(".");
		sb.setLength(sb.length()-1);
		res.add(sb.toString());
		return;        
	}
	if (cache[n][slot][slotSize]) return;
	
	// add slot
	String substr = s.substring(n, n+slotSize);
	int val = Integer.parseInt(substr);
	if(val <= 255 && !(substr.length() > 1 && substr.charAt(0)=='0')) {
		restored[slot] = val;
		dp(s, n-1, slot-1, 1, restored);
	}
	// continue slot
	dp(s, n-1, slot, slotSize+1, restored);
	cache[n][slot][slotSize] = true;
}
 
public List<String> restoreIpAddresses(String s) {
	res = new ArrayList<>();
	cache = new boolean[s.length()][4][4];
	dp(s, s.length()-1, 3, 1, new int[4]);
	return res;
}

Iterative Solution

public List<String> restoreIpAddresses(String s) {
	List<String> res = new ArrayList<String>();
	int len = s.length();
	for(int i = 1; i<4 && i<len-2; i++)
		for(int j = i+1; j<i+4 && j<len-1; j++)
			for(int k = j+1; k<j+4 && k<len; k++){
				String s1 = s.substring(0,i), s2 = s.substring(i,j), s3 = s.substring(j,k), s4 = s.substring(k,len);
				if(isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4))
					res.add(s1+"."+s2+"."+s3+"."+s4);
			}
	return res;
}
public boolean isValid(String s){
	if(s.length()>3 || s.length()==0 || (s.charAt(0)=='0' && s.length()>1) || Integer.parseInt(s)>255)
		return false;
	return true;
}

TC : $O(n^2)$ SC : $O(n^2)$