#include "s0093_restore_ip_addresses.hpp"

bool isValidIpAddressSegment(const string &s, int begin, int end) {
  if (begin > end) {
    return false;
  }
  if (s[begin] == '0' && begin != end) {  // 0开头的数字不合法
    return false;
  }
  int num = 0;
  for (int i = begin; i <= end; i++) {
    if (s[i] > '9' || s[i] < '0') {  // 遇到非数字字符不合法
      return false;
    }
    num = num * 10 + (s[i] - '0');
    if (num > 255) {  // 如果大于255了不合法
      return false;
    }
  }
  return true;
}

void restoreIpAddressesDFS(vector<int> &dots, vector<string> &result, string &s,
                           int startIndex) {
  // 结束条件
  if (dots.size() == 4 && startIndex == s.length()) {
    string ip = s.substr(0, dots[0] + 1) + "." +
                s.substr(dots[0] + 1, dots[1] - dots[0]) + "." +
                s.substr(dots[1] + 1, dots[2] - dots[1]) + "." +
                s.substr(dots[2] + 1, dots[3] - dots[2]);
    result.push_back(ip);
  }

  // 剪枝
  // 如果已经分成了四段，就没必要再分了
  if (dots.size() == 4) {
    return;
  }

  // 遍历当前节点的下一层
  for (int i = startIndex; i < startIndex + 3; ++i) {
    if (isValidIpAddressSegment(s, startIndex, i)) {
      dots.push_back(i);
      restoreIpAddressesDFS(dots, result, s, i + 1);
      dots.pop_back();
    }
  }
}

vector<string> S0093::restoreIpAddresses(string s) {
  vector<string> result{};
  vector<int> dots{};
  restoreIpAddressesDFS(dots, result, s, 0);
  return result;
}