LeetCode Q93: 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)

Solution, recursion. There are 4 sections in IP address in which there are at most 3 possible situations. Verify whether each case is valid.

	class Solution {
	public:
	vector<string> helper(string s, int curPos, int secId){
	vector<string> res;
	if(curPos>=s.length()||secId>4)
	return res;
	if(secId==4){
	if((s.length()-curPos>3) ||
	stoi(s.substr(curPos, s.length()-curPos))>255 ||
	(s.length()-curPos!=1 && s[curPos]=='0'))
	return res;
	res.push_back(string(".")+s.substr(curPos, s.length()-curPos));
	return res;
	}
	vector<string> r;
	for(int i=0; i<3; i++){
	if(s[curPos]=='0' && i!=0)
	continue;
	if(curPos+i<s.length() && stoi(s.substr(curPos, i+1))<=255){
	r=helper(s, curPos+i+1, secId+1);
	for(int j=0; j<r.size(); j++){
	string str=r[j];
	for(int k=i; k>=0; k--)
	str=s[curPos+k]+str;
	if(secId!=1)
	str=string(".")+str;
	res.push_back(str);
	}
	}
	}
	return res;
	}
	vector<string> restoreIpAddresses(string s) {
	vector<string> res;
	res=helper(s, 0, 1);
	return res;
	}
	};

view raw Q93RestoreIPAddress.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	void helper(vector<string>& res, string curRes, int idx, string s){
	if(idx>4) return;
	if(idx == 4&&s.length()==0){
	res.push_back(curRes);
	return;
	}
	int slen = s.length();
	for(int i=1; i<=3; i++){
	if(s.length()<i||(s[0]=='0'&&i>1))
	break;
	string ip = s.substr(0, i);
	if(stoi(ip)>255)
	break;
	string tmps = s.substr(i, slen-i);
	string tmpCurRes = curRes.length()==0? ip:curRes + string(".") + ip;
	helper(res, tmpCurRes, idx+1, tmps);
	}
	}
	vector<string> restoreIpAddresses(string s) {
	vector<string> res;
	string curRes;
	helper(res, curRes, 0, s);
	return res;
	}
	};

view raw Q93Rnd2.cpp hosted with ❤ by GitHub