C++ recursion solution


  • 0
    H
    vector<string> restoreIpAddresses(string s) {
        vector<string> v;
        string t;
        ip(v, t, s, 0, 4);
        return v;
    }
    void ip(vector<string>& v, string& t, string& s, int idx, int word) {
        int size  = s.length();
        int word3 = (--word)*3;
        
        for (int i=1; i<=3; ++i) {
            int left = size - idx - i;
            if (left >= word && left <= word3) {
                if (3 == i) {
                    string s255 = s.substr(idx, 3);
                    int i255 = atoi(s255.c_str());
                    if (i255 > 255) break;
                }
                
                if ('0' == s[idx] && 1 != i) break;
                
                string tt = t;
                for (int j=0; j<i; ++j) {
                    tt.push_back(s[idx+j]);
                }
                
                if (0 != word) {
                    tt.push_back('.');
                    ip(v, tt, s, idx+i, word);
                } else {
                    v.push_back(tt);
                }
            }
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.