93 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)

Solution

class Solution {
public:
    vector<string> IpHelper(string s, int i ) {
        int n = s.size();
        vector<string> res;
        vector<string> tmp_res;
        if ( n <= i-1 or n >= 3*i+1 ) return res;
        if ( i == 0 )  {res.push_back(""); return res;}
        for ( int j = 1; j <= min(3, n); j++ ) {
            string tmp_s = s.substr(0, j);
            int number = atoi(tmp_s.c_str());
            if ( number >= 256 ) continue;
            if ( tmp_s[0] == '0' and tmp_s.size() >= 2 ) continue;
            tmp_res = IpHelper(s.substr(j), i-1);
            int nres = tmp_res.size();
            if ( nres == 0 ) continue;
            for ( int k = 0; k <= nres-1; k++ ) {
                if ( tmp_res[k] == "") res.push_back(tmp_s);
                else res.push_back(tmp_s + "." + tmp_res[k]);
            }
        }
        return res;
    }
    vector<string> restoreIpAddresses(string s) {
        return IpHelper(s, 4);
    }
};

Notes: Pay attention to a lot of details when implementing.

• Check the validity of the "substring"

        if ( i >= 256 ) continue;
        if ( s[0] == '0' and s.size() >= 2 ) continue;
  

• Prune wisely for efficiency.

        if ( n <= i-1 or n >= 3*i+1 ) return res;
        if ( i == 0 )  {res.push_back(""); return res;}
  

• Practice, practice, and practice!