1
class Solution {
2
 public:
3
  vector<string> res;
4
  void dfs(string s, int idx, string curr_ip, int cnt) {
5
    if (cnt > 4) return;
6
    if (cnt == 4 && idx == s.size()) {
7
      res.push_back(curr_ip);
8
      // return;
9
    }
10
    for (int i = 1; i < 4; i++) {
11
      if (idx + i > s.size()) break;
12
      string str = s.substr(idx, i);
13
      if ((str[0] == '0' && str.size() > 1) || (i == 3 && stoi(str) >= 256)) continue;
14
      dfs(s, idx + i, curr_ip + str + (cnt == 3 ? "" : "."), cnt + 1);
15
    }
16
  }
17
  vector<string> restoreIpAddresses(string s) {
18
    dfs(s, 0, "", 0);
19
    return res;
20
  }
21
};