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)

 

C++:
01 void restoreIP(vector<string>& result,string s,int d,string cur)
02 {
03     int n=s.size();
04     if((n==0)||(n>(d+1)*3)||(n<d+1))
05         return;
06     int tmp=0;
07     if(d==0){
08         for(int i=0;i<n;i++){
09             tmp=tmp*10+s[i]'0';
10             if((tmp==0)&&(i<n1))
11                 return;
12         }
13         if(tmp>255)
14             return;
15         else{
16             cur+=s;
17             result.push_back(cur);
18         }
19     }else if(d>0){
20         for(int i=0;i<n;i++){
21             tmp=tmp*10+s[i]'0';
22             if(tmp>255)
23                 break;
24             string h=cur+s.substr(0,i+1)+'.';
25             restoreIP(result,s.substr(i+1,ni1),d1,h);
26             if(tmp==0)
27                 break;
28         }
29     }
30 }
31 
32  vector<string> restoreIpAddresses(string s)
33  {
34       vector<string> result;
35       string cur;
36       restoreIP(result,s,3,cur);
37       return result;
38 }
Advertisements
This entry was posted in Recursive, String. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s