Restore IP Addresses (Java)

LeetCode

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

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

Solution:

DFS to combine each possible result, meanwhile skip all impossible combination for result, such as

rest letters in s can not be more than 3* rest parts and rest letters can not be less than rest parts.

	/*
	Given a string containing only digits,
	restore it by returning all possible valid IP address combinations.
	For example:
	Given "25525511135",
	return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
	*/
	public class RestoreIPAddresses {
	public ArrayList<String> restoreIpAddresses(String s) {
	ArrayList<String> result=new ArrayList<String>();
	if (s==null||s.length()>12|| s.length()<4){
	return result;
	}
	String ip="";
	// record current index of s
	int i=0;
	// ip can be split into 4 parts, parNum is indicated which part it is
	int partNum=0;
	// DFS
	buildResult(s, i,ip, partNum, result);
	return result;
	}
	private void buildResult(String s, int i, String ip, int partNum, ArrayList<String> result){
	if (i==s.length() && partNum==4){
	StringBuilder sb=new StringBuilder(ip);
	sb.deleteCharAt(sb.length()-1);
	result.add(sb.toString());
	return;
	}
	int num=0;
	for (int j=i; j<i+3 && j<s.length(); j++){
	if (s.length()-j<4-partNum){
	// left letter number less than the need to fill all left parts
	return;
	}
	if (s.length()-j>(4-partNum)*3){
	// left parts can not hold all left letters
	return;
	}
	num=num*10+(s.charAt(j)-'0');
	if (num<=255){
	ip+=s.charAt(j);
	buildResult(s, j+1, ip+'.', partNum+1, result );
	}
	// skill all situation that the head of each part is start with 0, except only 0
	// at this section.
	/*
	example:
	Input: "010010"
	Output: ["0.1.0.0110","0.1.00.110","0.1.001.0","0.110.0.110","0.110.01.0","0.110100.1.0","01.0.0.110","01.0.01.0","01.00.1.0","0110.0.1.0"]
	Expected: ["0.10.0.10","0.100.1.0"]
	*/
	if (num==0){
	break;
	}
	}
	}
	}

view raw RestoreIPAddresses.java hosted with ❤ by GitHub