学步园

题目描述：

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)

因为给的子串最多就只能有3*4=12个，所以可以用简单的递归来做而不用担心超时。

#define vs vector<string>
class Solution {
public:
    
vs restoreIpAddresses(string s)
{
    vs ans;
	string tmp;
	restore(s,0,1,tmp,ans);
	return ans;
}
void restore(string& s,int cur,int kth,string& tmp,vs& ans)
{
	if ( cur==s.size() || kth==5)
	{
		if ( cur==s.size()&& kth==5)
			ans.push_back(tmp);
		return ;
	}
	int diff=s.size()-cur;
	if ( diff<4-kth+1 ||  diff> (4-kth+1)*3)
		return ;
        
    	
	//get only one char
	tmp.append(string(1,s[cur]));
    if ( kth!=4)
	    tmp.append(".");
	restore(s,cur+1,kth+1,tmp,ans);
	tmp.pop_back();
    if ( kth!=4)
	    tmp.pop_back();

    if ( s[cur]=='0')
        return;
        
	//two chars
	if ( cur<s.size()-1)
	{
		int iIP=(s[cur]-'0')*10+s[cur+1]-'0';
		if ( iIP<=255)
		{
			tmp.append(string(1,s[cur]));
			tmp.append(string(1,s[cur+1]));
            if ( kth!=4)
			    tmp.append(".");
			restore(s,cur+2,kth+1,tmp,ans);
			tmp.pop_back();
			tmp.pop_back();
            if ( kth!=4)
			    tmp.pop_back();
		}
	}
	//three chars
	if ( cur<s.size()-2)
	{
		int iIP=(s[cur]-'0')*100+(s[cur+1]-'0')*10+s[cur+2]-'0';
		if ( iIP<=255)
		{
			tmp.append(string(1,s[cur]));
			tmp.append(string(1,s[cur+1]));
			tmp.append(string(1,s[cur+2]));
			if ( kth!=4)
                tmp.append(".");
			restore(s,cur+3,kth+1,tmp,ans);
			tmp.pop_back();
			tmp.pop_back();
			tmp.pop_back();
            if ( kth!=4)
			    tmp.pop_back();
		}
	}
}
	
};