My standard backtracking solution!


  • 0
    P
    void restoreIP(string &s, int start, int level, vector<string> & ans) {
        if (level == 3) {
            ans.push_back(s);
            return;
        }
        for (int i = 1;i <= 3;++i) {
            if (start+i+2-level >= s.size() || stoi(s.substr(start,i)) > 255)
                break;
            if (s[start] == '0' && i > 1)
                break;
            if (level == 2 && s[start+i] == '0' && start+i != s.size()-1)
                continue;
            if (level == 2 && (s.size() - (start+i) > 3  || stoi(s.substr(start+i)) > 255))
                continue;
            s.insert(start+i,1,'.');
            restoreIP(s,start+i+1,level+1,ans);
            s = s.erase(start+i,1);
        }
    }
    
    vector<string> restoreIpAddresses(string s) {
        vector<string> ans;
        restoreIP(s,0,0,ans);
        return ans;
    }

Log in to reply
 

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