Restore IP Addresses Solutions in C++

// Source : https://oj.leetcode.com/problems/restore-ip-addresses/
// Author : Hao Chen
// Date   : 2014-08-26



#include <stdlib.h>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

void restoreIpAddressesHelper(string& s, int start, int partNum, string ip, vector<string>& result);

vector<string> restoreIpAddresses(string s) {
    vector<string> result;
    string ip;
    restoreIpAddressesHelper(s, 0, 0, ip, result);
    return result;
}

void restoreIpAddressesHelper(string& s, int start, int partNum, string ip, vector<string>& result) {

    int len = s.size();
    if ( len - start < 4-partNum  || len - start > (4-partNum)*3 ) {
        return;
    }

    if (partNum == 4 && start == len){
        ip.erase(ip.end()-1, ip.end());
        result.push_back(ip);
        return;
    }

    int num = 0;
    for (int i=start; i<start+3; i++){
        num = num*10 + s[i]-'0';
        if (num<256){
            ip+=s[i];
            restoreIpAddressesHelper(s, i+1, partNum+1, ip+'.', result);
        }         
        //0.0.0.0 valid, but 0.1.010.01 is not
        if (num == 0) {
            break;
        }
    }
       
}


int main(int argc, char**argv)
{
    string s = "25525511135";
    if (argc>1){
        s = argv[1];
    }

    vector<string> result = restoreIpAddresses(s);

    cout << s << endl;
    for(int i=0; i<result.size(); i++){
        cout << '\t' << result[i] << endl;
    }
    return 0;
}

#include <vector>
using std::vector;
#include <string>
using std::string;

class Solution {
    vector<string> ret;

    bool valid(const string &s) {
        if (s.size() > 1 && s[0] == '0') return false;
        int num = std::stoi(s);
        return 0 <= num && num <= 255;
    }

    void restore(const string &origin, const string &ip, int part)
    {
        if (part == 0) {
            if (origin.empty()) ret.push_back(ip);
            return;
        }

        for (size_t i=1; i<4; ++i) {
            if (origin.size() < i) break;
            string section = origin.substr(0, i);
            if (valid(section)) {
                if (part != 1) section.append(".");
                restore(origin.substr(i), ip+section, part-1);
            }
        }
    }

public:
    vector<string> restoreIpAddresses(string s) {
        if (s.size() >= 4 && s.size() <= 12) restore(s, "", 4);
        return ret;
    }
};

/// Source : https://leetcode.com/problems/restore-ip-addresses/
/// Author : liuyubobobo
/// Time   : 2019-01-18

#include <iostream>
#include <vector>

using namespace std;


/// Backtrack
/// Time Complexity: O(2^n)
/// Space Complexity: O(n)
class Solution {
public:
    vector<string> restoreIpAddresses(string s) {

        vector<string> res;
        vector<int> ip;
        dfs(s, 0, ip, res);
        return res;
    }

private:
    void dfs(const string& s, int index, vector<int>& ip, vector<string>& res){

        if(index == s.size()){
            if(ip.size() == 4)
                res.push_back(get_string(ip));
            return;
        }

        if(index == 0){
            ip.push_back(s[0] - '0');
            dfs(s, index + 1, ip, res);
        }
        else{
            int next = ip.back() * 10 + (s[index] - '0');
            if(next <= 255 && ip.back() != 0){
                ip.back() = next;
                dfs(s, index + 1, ip, res);
                ip.back() /= 10;
            }
            if(ip.size() < 4){
                ip.push_back(s[index] - '0');
                dfs(s, index + 1, ip, res);
                ip.pop_back();
            }
        }
    }

    string get_string(const vector<int>& ip){
        string res = to_string(ip[0]);
        for(int i = 1; i < ip.size(); i ++)
            res += "." + to_string(ip[i]);
        return res;
    }
};


void print_vec(const vector<string>& vec){

    for(const string& e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    string s1 = "25525511135";
    print_vec(Solution().restoreIpAddresses(s1));
    // 255.255.111.35 255.255.11.135

    string s2 = "1";
    print_vec(Solution().restoreIpAddresses(s2));
    // empty

    string s3 = "010010";
    print_vec(Solution().restoreIpAddresses(s3));
    // 0.10.0.10 0.100.1.0

    return 0;
}