Restore IP Addresses

Solutions

Backtracking

Time: O(2^n)Space: O(n)

The solution uses a backtracking approach to generate all possible valid IP addresses. It iterates over the string and tries to split it into four sections. For each section, it checks if the section is valid (i.e., it does not start with '0' unless it is '0' itself, and its value is not greater than 255). If the section is valid, it adds it to the current path and recursively calls the backtrack function with the remaining string. If the path has four sections and the remaining string is empty, it adds the path to the result list.

vector<string> restoreIpAddresses(string s) {
  vector<string> res;
  vector<string> path;
  backtrack(s, path, res);
  return res;
}
void backtrack(string s, vector<string>& path, vector<string>& res) {
  if (path.size() == 4) {
    if (s.length() == 0) {
      string ip;
      for (int i = 0;
      i < path.size();
      i++) {
        ip += path[i];
        if (i < path.size() - 1) {
          ip += ".";
        }
      }
      res.push_back(ip);
    }
    return;
  }
  for (int i = 1;
  i <= 3;
  i++) {
    if (s.length() < i) {
      break;
    }
    string cur = s.substr(0, i);
    if ((cur.length() > 1 && cur[0] == '0') || stoi(cur) > 255) {
      continue;
    }
    path.push_back(cur);
    backtrack(s.substr(i), path, res);
    path.pop_back();
  }
}

Constraints:

Examples:

Solutions

Backtracking

Follow-up: