LeetCode

2013.12.31 18:06

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:

　　Given a number string, find all of the possible IP address that it may represent in decimal form.

　　Finding all possible answer means we usually have to do a search, either DFS or BFS. This problem can be properly solved with DFS.

　　Time complexity is O(2^n), space compelxity is O(2^n) as well, where n is the length of the string. Luckily the actual compelxity is much lower than 2^n, as each token in the ip address ranges in [0, 255], this natural limit helps us trim a lot of invalid search paths. By the way, the length n can be at most 12 (255.255.255.255), since the ip here only refers to IPv4, not including IPv6.

Accepted code:

 1 //#define __MAIN__
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <string>
 6 #include <vector>
 7 using namespace std;
 8 
 9 class Solution {
10 public:
11     vector<string> restoreIpAddresses(string s) {
12         // Note: The Solution object is instantiated only once and is reused by each test case.
13         str = s.data();
14         slen = strlen(str);
15         res.clear();
16         if(slen > 12){
17             return res;
18         }
19         dfs(0, 0);
20         
21         return res;
22     }
23 private:
24     int slen;
25     int a[4];
26     vector<string> res;
27     const char *str;
28     char tmp[100];
29 
30     void dfs(int si, int ai) {
31         int i;
32         int num;
33         string snum;
34         
35         if(ai == 4){
36             if(si == slen){
37                 sprintf(tmp, "%d.%d.%d.%d", a[0], a[1], a[2], a[3]);
38                 res.push_back(string(tmp));
39             }
40             return;
41         }
42         
43         if(si >= slen){
44             return;
45         }
46         
47         if(ai + (slen - si) / 3 > 4){
48             return;
49         }
50         
51         num = 0;
52         snum = "";
53         for(i = si; i < si + 3 && i < slen; ++i){
54             if(snum.length() > 0 && snum[0] == '0'){
55                 //cannot add more digits after leading 0
56                 break;
57             }
58             num = num * 10 + (str[i] - '0');
59             snum = snum + str[i];
60             if(num > 255){
61                 break;
62             }else{
63                 a[ai] = num;
64                 dfs(i + 1, ai + 1);
65             }
66         }
67     }
68 };
69 
70 #ifdef __MAIN__
71 #include <iostream>
72 int main()
73 {
74     Solution sol;
75     char str[100];
76     vector<string> res;
77     int i;
78 
79     while(gets(str) != NULL){
80         res = sol.restoreIpAddresses(string(str));
81         cout << "res_count = " << res.size() << endl;
82         for(i = 0; i < res.size(); ++i){
83             cout << res[i] << endl;
84         }
85         cout << endl;
86     }
87 
88     return 0;
89 }
90 #endif