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 restoreIpAddressHelper(string s, int p, int t,
02                        vector<string>& result, string tmp)
03 {
04     int n=s.size();
05     if((np>3*t)||(np<t))
06         return;
07     if(t==1)
08     {
09         if((s[p]==‘0’)&&(p!=n1))
10             return;
11         string a=s.substr(p);
12         int k=stoi(a);
13         if((k<0)||(k>255))
14             return;
15         tmp+=a;
16         result.push_back(tmp);
17         return;
18     }
19     for(int i=1;i<=3;i++)
20     {
21         if(s[p]==‘0’)
22         {
23             string item=tmp+‘0’+‘.’;
24             restoreIpAddressHelper(s,p+1,t1,result,item);
25             break;
26         }
27         string a=s.substr(p,i);
28         int k=stoi(a);
29         if((k>255)||(k<pow(10,(i1))))
30             return;
31         string item=tmp+a+‘.’;
32         restoreIpAddressHelper(s,p+i,t1,result,item);
33     }
34 }
35 class Solution {
36 public:
37     vector<string> restoreIpAddresses(string s) {
38         // Start typing your C/C++ solution below
39         // DO NOT write int main() function
40         vector<string> result;
41         string tmp;
42         restoreIpAddressHelper(s, 0, 4, result, tmp);
43         return result;
44     }
45 };
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