My AC solution using c++, 4ms


  • 0
    Z

    my 4ms solution,

        int addr_len[4];
    
    void doRestore(vector<string> &ret, string &s, int start, int k)
    {
    	if (start >= s.length()) return;
    
    	if (k == 1){
    		if (s.length() - start > 3)  return;
    
    		int val = atoi(s.substr(start, s.length() - start).c_str());
    		if (val >= 0 && val <= 255){
    			if ((s[start] == '0') && (s.length() - start != 1)) return;
    			
    			string str;
    			int pos = 0;
    
    			for (int i = 0; i <= 2; i++){
    				str += s.substr(pos, addr_len[i]) + ".";
    				pos += addr_len[i];
    			}
    			str += s.substr(start, s.length() - start);
    
    			ret.push_back(str);
    		}
    	}
    	else{
    		int len = s.length() - start > 3 ? 3 : s.length() - start;
    
    		for (int i = 1; i <= len; i++){
    			int val = atoi(s.substr(start, i).c_str());
    			if (val >= 0 && val <= 255){
    				addr_len[4 - k] = i;
    				doRestore(ret, s, start + i, k - 1);
    				
    				if (val == 0)   break;
    			}
    		}
    	}
    }
    
    vector<string> restoreIpAddresses(string s) {
    	vector<string> ret;
    
    	doRestore(ret, s, 0, 4);
    
    	return ret;
    }

Log in to reply
 

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