Leetcode典型题解答和分析、归纳和汇总——T93（复原IP地址）

问题描述：

给定一个只包含数字的字符串，复原它并返回所有可能的IP地址格式。

问题分析：
采用回溯算法进行求解。

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     
	
      vector<
      string> restoreIpAddresses(
      string s) {
     
    
   

    

     

    
    

     
		
      string ip;
     
    
   

    

     

    
    

     

      		helper(s, 
      0, ip);
     
    
   

    

     

    
    

     
		
      return res;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	
      void helper(string s, int n, string ip) {
     
    
   

    

     

    
    

     
		
      if (n == 
      4) {
     
    
   

    

     

    
    

     
			
      if (s.empty()) res.push_back(ip);   
      //当已经有3个数字可以作为一个字节，并且s字符串为空
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		
      else {
     
    
   

    

     

    
    

     
			
      for (
      int k = 
      1; k < 
      4; ++k) {
     
    
   

    

     

    
    

     
				
      if (s.size() < k) 
      break;    
      //当长度不够，直接退出
     
    
   

    

     

    
    

     
				
      int val = stoi(s.substr(
      0, k));  
      //stoi表示将string类型数据转换成int类型数据
     
    
   

    

     

    
    

     
				
      if (val > 
      255 || k != 
      std::to_string(val).size()) 
      continue; 
      //剪枝
     
    
   

    

     

    
    

     

      				helper(s.substr(k), n + 
      1, ip + s.substr(
      0, k) + (n == 
      3 ? 
      "" : 
      "."));  
      //s.substr(0, k) + (n == 3 ? "" : ".")是字符串的连接操作，不是整数
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		
      return;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      private:
     
    
   

    

     

    
    

     
	
      vector<
      string> res;
     
    
   

    

     

    
    

     

      };