Restore IP Addresses

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)

-------------------------- thinking ------------------------------------
https://oj.leetcode.com/discuss/12790/my-code-in-java
in the question, we are not allowing the situation of "027" valid as the normal natural number

--------------------------- codes --------------------------------------
 class Solution {
 public:
     vector<string> restoreIpAddresses(string s) {
         vector<string> result;
         if (s.size() < 4) {
             return result;
         }
         for (int ip1 = 0; ip1 < s.size() - 3; ip1++) {
             if (isNotValid(s.substr(0, ip1+1))) {
                 break;
             }
             for (int ip2 = ip1 + 1; ip2 < s.size() - 2; ip2++) {
                 if (isNotValid(s.substr(ip1+1, ip2 - ip1))) {
                     break;
                 }
                 for (int ip3 = ip2 + 1; ip3 < s.size() - 1; ip3++) {
                     if (isNotValid(s.substr(ip2+1, ip3 - ip2))) {
                         break;
                     }
                     if (!isNotValid(s.substr(ip3+1, s.size()))) {
                         string rlt = s.substr(0, ip1+1) + "." + s.substr(ip1+1, ip2-ip1) + "." + s.substr(ip2+1, ip3-ip2) + "." + s.substr(ip3+1, s.size());
                         result.push_back(rlt);
                     }
                 }
             }
         }
         return result;
     }
     bool isNotValid(string s) {
         if (s.size() == 0) {
             return true;
         }
         //int i;
         //for (i = 0; i < s.size(); i++) {
         //    if (s[i] != '0') {
         //        break;
         //    }
         //}
         //s = s.substr(i, s.size()-i);
         //if (s.size() == 0) {
         //    return false;
         //}
         if (s.size() > 3 || s.size() == 0 || (s[0] == '0' && s.size() > 1) || stoi(s) > 255) {
             return true;
         }
         return false;
     }
 };

----------------------------- recursive codes --------------------------------------
 class Solution {
 public:
     vector<string> restoreIpAddresses(string s) {
         vector<vector<int>> out_num;
         vector<int> tmp_num;
        restoreHelper(s, 0, 0, out_num, tmp_num);
        vector<string> result;
        for (int i = 0; i < out_num.size(); i++) {
            string ele = s.substr(0, out_num[i][0]) + ".";
            for (int j = 0; j < 2; j++) {
                ele += s.substr(out_num[i][j], out_num[i][j+1] - out_num[i][j]);
                ele += ".";
            }
            ele += s.substr(out_num[i][2], s.size());
            result.push_back(ele);
        }
        return result;
     }
     void restoreHelper(string s, int start, int count, vector<vector<int>> &out_num, vector<int> &tmp_num) {
         if (tmp_num.size() == 3) {
             if (isValid(s.substr(start, s.size() - start))) {
                 // bug here
                 //tmp_num.push_back(start);
                 out_num.push_back(tmp_num);
             }
             return;
         }
             for (int i = start + 1; i < s.size(); i++) {
                 if (isValid(s.substr(start, i - start))) {
                     tmp_num.push_back(i);
                     restoreHelper(s, i, count, out_num, tmp_num);
                     //bug here
                     tmp_num.pop_back();
                 } else {
                     break;
                 }
             }
     }
     bool isValid(string s) {
         if (s.size() == 0 || s.size() > 3 || (s.size() > 1 && s[0] == '0') || stoi(s) > 255) {
             return false;
         }
         return true;
     }
 };