My Accepted 5ms C++ solution


  • -1
    C
    vector<string> restoreIpAddresses(string s) 
    {
    	vector<string> storeIpAddressVec;
    	int charCounts[4] = {0,0,0,0};
    	int curLayer = 0;// Current calculation layer in solution space. There are 4 layers from 0-3 corresponding to the array charCounts.
    	int headIndex = 0;// The loop end check point.
    	//bool allZeroYn = true;
    
    	// if length of s is out of range, return directly.
    	if (s.size() > 12 || s.size() < 4)
    	{
    		return storeIpAddressVec;
    	}
    
    	// Find the position of loop end check point. The first point which is not 0.
    	for (int i =0; i < s.size();++i)
    	{
    		if (s[i] == '0')
    		{
    			charCounts[headIndex] = 1;
    			headIndex++;
    			continue;;
    		}
    		else
    		{
    			break;
    		}
    	}
    
    	if (headIndex == 4)
    	{
    		if (s.size() == 4)
    		{
    			storeIpAddressVec.push_back("0.0.0.0");
    			return storeIpAddressVec;
    		}
    		else
    		{
    			return storeIpAddressVec;
    		}
    		
    	}
    	// Start from the headIndex
    	curLayer = headIndex;
    		
    	while(true)
    	{
    		int totalLen = charCounts[0] + charCounts[1] + charCounts[2] + charCounts[3];
    		if (charCounts[curLayer]+1 > 3 || totalLen >= s.size())
    		{
    			string strTmp = "";
    			// Back track to the last non-zero begin section
    			while(curLayer >= headIndex)
    			{
    				int baseIndex = 0;
    				// It doesn't check itself
    				curLayer--;
    				for (int i = 0;i < curLayer;i++)
    				{
    					baseIndex += charCounts[i];
    				}
    				strTmp = s.substr(baseIndex,charCounts[curLayer]);
    
    				if (strTmp[0] != '0')
    				{ 
    					break;
    				}
    				
    			}
    
    			// When backtrack to the root node means all paths has traveled.
    			if (curLayer < headIndex)
    			{
    				break;
    			}
    			// Set the sections after curLayer to zero.
    			for (int i = curLayer+1;i < 4;++i)
    			{
    				charCounts[i] = 0;
    			}
    			continue;
    		}
    		else
    		{
    			// Add current layer length
    			charCounts[curLayer] += 1;
    			totalLen = charCounts[0] + charCounts[1] + charCounts[2] + charCounts[3];
    			if (curLayer < 4)
    			{
    				int curBaseIndex = 0;
    				string curIPSectionStr = "";
    				int leftLen = s.size() - totalLen;;
    				// Calculate the current base index.
    				for (int i = 0;i < curLayer; i++)
    				{
    					curBaseIndex += charCounts[i];
    				}
    				// Get the current assigned section string
    				curIPSectionStr = s.substr(curBaseIndex,charCounts[curLayer]);
    
    				// Check if the current dispatch is valid. If no, re-assign current layer.
    				if (curIPSectionStr.length() < 3 || curIPSectionStr.compare( "255") <= 0)
    				{
    					// 0 should be single number, each IP section can not be a number begin with zero.
    					if (curIPSectionStr[0] == '0')
    					{
    						charCounts[curLayer] = 1;
    						totalLen = charCounts[0] + charCounts[1] + charCounts[2] + charCounts[3];
    						leftLen = s.size() - totalLen;
    					}
    
    					// if leftLen is just needed, the dispatch the left directly and check if this dispatch is correct. 
    					// If this pre-dispatch is not correct then need re-assign current layer.
    					 if (leftLen == (3-curLayer)*3)
    					{
    						bool isSuccess = true;
    						bool bContainZero = false;
    						string strTmp = "";
    						
    						// Dispatch the string directly
    						for (int i = curLayer+1;i < 4;i++)
    						{
    							charCounts[i] = 3;
    						}
    
    						// out put
    						for (int k = curLayer+1;k < 4;k++)
    						{
    							int baseIndex = 0;
    							for (int i = 0;i < k;i++)
    							{
    								baseIndex += charCounts[i];
    							}
    							strTmp = s.substr(baseIndex,charCounts[k]);
    							if ((strTmp.size() == 3 && strTmp.compare( "255") > 0) || strTmp[0] == '0')
    							{
    								isSuccess = false;
    							}
    							if (strTmp[0] == '0')
    							{
    								bContainZero = true;
    							}
    						}
    
    						if (isSuccess)
    						{
    							int baseIndex = 0;
    							string strTmp = "";
    							// out put
    							for (int k = 0;k < 4;k++)
    							{
    								strTmp += s.substr(baseIndex,charCounts[k]);
    								baseIndex += charCounts[k];
    								if (k != 3)
    								{
    									strTmp += ".";
    								}
    
    							}
    							// Track back from 3th layer.
    							curLayer = 3;
    							storeIpAddressVec.push_back(strTmp);
    							continue;
    						}
    						else
    						{
    							string strTmp = "";
    							// Back track to the last non-zero begin section
    							while(curLayer >= headIndex)
    							{
    								int baseIndex = 0;
    								for (int i = 0;i < curLayer;i++)
    								{
    									baseIndex += charCounts[i];
    								}
    								strTmp = s.substr(baseIndex,charCounts[curLayer]);
    
    								if (strTmp[0] != '0')
    								{ 
    									break;
    								}
    								curLayer--;
    							}
    
    							// When backtrack to the root node means all paths has traveled.
    							if (curLayer < headIndex && strTmp.size() == 3)
    							{
    								break;
    							}
    							// Set the sections after curLayer to zero.
    							for (int i = curLayer+1;i < 4;++i)
    							{
    								charCounts[i] = 0;
    							}
    							continue;
    						}
    					}// if leftLen is more then needed, the dispatch more length for current layer. // re-assign current layer.
    					else if (leftLen > (3-curLayer)*3)
    					{
    						string strTmp = "";
    						// Back track to the last non-zero begin section
    						while(curLayer >= headIndex)
    						{
    							int baseIndex = 0;
    							for (int i = 0;i < curLayer;i++)
    							{
    								baseIndex += charCounts[i];
    							}
    							strTmp = s.substr(baseIndex,charCounts[curLayer]);
    							
    							if (strTmp[0] != '0')
    							{ 
    								break;
    							}
    							curLayer--;
    						}
    
    						// When backtrack to the root node means all paths has traveled.
    						if (curLayer < headIndex && strTmp.size() == 3)
    						{
    							break;
    						}
    						// Set the sections after curLayer to zero.
    						for (int i = curLayer+1;i < 4;++i)
    						{
    							charCounts[i] = 0;
    						}
    						continue;
    					}
    					else // if leftLen is enough for needed, the go ahead to search next solution
    					{
    						curLayer++;
    						for (int i = curLayer+1;i < 4;++i)
    						{
    							charCounts[i] = 0;
    						}
    						continue;
    					}
    					
    				}
    				else // If current assigned section is bigger the '255', we need track back to pre-layer.
    				{
    					for (int i = curLayer+1;i < 4;++i)
    					{
    						charCounts[i] = 0;
    					}
    					continue;
    				}
    			}
    		}
    	}
    
    	return storeIpAddressVec;
    }

Log in to reply
 

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