C++ 0ms solution


  • 0
    R

    The idea is: iteratively find the three position to partition the string
    One key point for this problem is to avoid "010" this kind of number, which is not valid.

    vector<string> restoreIpAddresses(string s) {
        vector<string> ret;
        for (int i = 0, s1 = 0; i < 3 & i+3 < s.size(); ++i) {
            s1 = s1*10 + s[i] - '0';
            if(s1 > 255) break;
            for (int j = i+1, s2 = 0; j < i+4 && j+2 < s.size(); ++j) {
                s2 = s2*10 + s[j] - '0';
                if (s2 > 255) break;
                for (int k = j+1, s3 = 0; k < j+4 && k+1 < s.size(); ++k) {
                    s3 = s3*10 + s[k] - '0';
                    if (s3 > 255) break;
                    if (s.size()-k-1 < 4 && stoi(s.substr(k+1)) < 256 && !(s.size()-k-1 > 1 && s[k+1] == '0')) {
                        ret.push_back(s.substr(0,i+1)+"."+s.substr(i+1,j-i)+"."+s.substr(j+1,k-j)+"."+s.substr(k+1));
                    }
                    if (s[j+1] == '0') break;
                }
                if (s[i+1] == '0') break;
            }
            if (s[0] == '0') break;
        }
        return ret;
    }

Log in to reply
 

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