本文共 1737 字，大约阅读时间需要 5 分钟。

题目描述

给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。

示例 1：

输入：s = “25525511135”

输出：[“255.255.11.135”,“255.255.111.35”]

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/restore-ip-addresses 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

C++

时间复杂度：O(3^segcount*|s|)

class Solution {
       /*    IP地址：A.B.C.D    每次做选择，然后判断是否可以，回溯    */public:    vector 
   
     res;     vector
    
      restoreIpAddresses(string s) {
           vector
     
       track;  //路径        if(s.size()>12 ||s.size()<4)            return res;        traverse(track,s,1,0);        return res;    }    //index表示剩余字符串的开头；seg_index，一共有四个段，1，2，3，4 标识要选择第几段    void traverse(vector
      
       & track,string s,int seg_indx,int index){
           //回溯结束条件        if(seg_indx==5){
               string ss=track[0];            for(int i=1;i<4;i++){
                   ss+=".";                ss+=track[i];            }            res.push_back(ss);            return ;        }        //做选择,选择空间只有1，2，3位        for(int i=index;i
       
        1)                continue;                //长度为12时，第一段必须为3个字符，否则后边会超                    //此处为我的理解难点，对于剩余的字符个数需要满足如下条件                        //第一个条件：每段至少分一个，                        //第二个条件：每段最多分3个            if(s.length()-1-i<4-seg_indx||s.length()-1-i>3*(4-seg_indx))                continue;                 //数值大小必须在[0,255]之间             if(atoi(seg.c_str())>255)                continue;            track.push_back(seg);            traverse(track,s,seg_indx+1,i+1);            //撤销选择            track.pop_back();        }                    }};