Leetcode problem: Recover IP Addresses

recover_ip_address.cpp

/*
 * This is a classic backtracking algorithm. It is made difficult due to the following:
 * 1) There is a special case, namely 0
 * 2) Normally, backtracking employs a for loop, this needs a while loop. Therefore
 *    conditions for ending the recursion is not normal
 *
 * All ip addresses consist of octets, which is between 0 and 255. So any number within this
 * range should be selected for our ip address. If however we cannot pick such a number
 * then we must back track
 * Time Complexity O(n^2) Space O(1)
 */

class Solution {
public:
    
    void getAllIpAddresses(vector<string>& ips, vector<int>& octets, const string& s, int start) {

        if (octets.size() == 4) {
            if (start < s.size()) { //All octets are filled but not whole string has been used
                return;
            }
            
            //Use a string stream to convert from integers back to string
            stringstream ss;
            for (int i=0; i < 4; i++) {
                ss << octets[i];
                if (i < 3) ss <<".";
            }
            ips.push_back(ss.str());
            return;
        }
        
        int octet = 0;

        //Special Case: 0
        if (!int(s[start]-'0')) {
            octets.push_back(0);
            getAllIpAddresses(ips, octets, s, start+1);
            octets.pop_back();
        } else {    
            while (octet*10 + int(s[start]-'0') > 0 && octet*10 + int(s[start]-'0') <= 255) {
                if (start < s.size()) {
                    octet *=10;
                    octet += int(s[start++]-'0');
                    octets.push_back(octet);
                    getAllIpAddresses(ips, octets, s, start);
                    octets.pop_back();
                } else break;
            }
        }
    }


    vector<string> restoreIpAddresses(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<string> ips;
        vector<int> octets;
        getAllIpAddresses(ips, octets, s, 0);
        
        return ips;
    }
};