[LeetCode83]Restore IP Addresses

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)
Analysis:
차례로 숫자열을 네 부분으로 나누고 각 부분은 0<=p<=255를 만족시킨다.예를 들어 010은 재미없는 것이다. "0.10.010.1"이다.
Java

public class Solution {
    public List<String> restoreIpAddresses(String s) {
		List<String> res = getIPAdd(s,4);
		if(res == null) res = new ArrayList<>();
		return res;
	}
	public ArrayList<String> getIPAdd(String s, int k){
		assert(k<=4 && k>=1);
		if(s==null || s.length()<k || s.length()>3*k) return null;
		ArrayList<String> res = new ArrayList<>();
		for(int i=0;i<Math.min(s.length(), 3);i++){
			String num = s.substring(0, i+1);
			if((i==0 || num.charAt(0)>'0')&& Integer.parseInt(num)<=255){
				if(k==1){
					if(i==s.length()-1)
						res.add(num);
				}else {
					ArrayList<String> remain = getIPAdd(s.substring(i+1), k-1);
					if(remain!=null){
						for(String r:remain){
							String temp = num+'.'+r;
							res.add(temp);
						}
					}
				}
			}else
				break;
		}
		return res;
	}
}

c++

class Solution {
public:
    /*
s -- string, input
start -- startindex, start from which index in s
step -- step current step index, start from 0, valid value1-4,4 means the end
ip -- intermediate, split result in current spliting process
result -- save all possible ip address
*/
void dfsIp(string s, size_t start, size_t step, string ip,
           vector<string> &result){
    if(start == s.size() && step == 4){//find a possible result
        ip.resize(ip.size()-1);
        result.push_back(ip);
        return;
    }
    //since each part of IP address is in 0..255,the leagth of each
    // part is less than 3 and more than 0
    if(s.size()-start > (4-step)*3) return;
    if(s.size()-start < (4-step)) return;

    int num=0;
    for(size_t i=start;i<start+3;i++){
        num = num*10 + (s[i]-'0');
        if(num<=255){
            ip+=s[i];
            dfsIp(s,i+1,step+1,ip+'.',result);
        }
        if(num == 0) break;
    }
}
vector<string> restoreIpAddresses(string s) {
    vector<string> result;
    string ip; // save temporaty result in processing
    dfsIp(s,0,0,ip,result);
    return result;
}
};