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

一天一道LeetCode

本系列文章已全部上传至我的github，地址：

欢迎大家关注我的新浪微博，

欢迎转载，转载请注明出处

（一）题目

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:

Given “25525511135”,

return [“255.255.11.135”, “255.255.111.35”]. (Order does not matter)

（二）解题

题目大意：给定一串字符，判断可以组成多少个有效的ip地址

解题过程中需要注意无效ip，诸如00，010等

解题思路：采用回溯法，ip有四级，分别判断每一级是否为有效的，依次递归，到最后判断能不能组成有效ip，没有就回溯到上一级继续递归。详细思路见代码注释

class Solution {public:    vector
   
     restoreIpAddresses(string s) {        vector
    
      ret;        string ip;        dfsRestoreIp(s,ip,0,0,ret);        return ret;    }    void dfsRestoreIp(string& s , string ip , int count , int i ,vector
     
      &ret)    {        if(count==4)//计数到4后表示一个ip地址        {            if(i==s.length()) {                ip.erase(ip.end()-1);//去除最后的'.'                ret.push_back(ip);            }            return;        }        int num = 0;        for(int j = i ; j < s.length() ; j++)        {            ip+=s[j];            num = num*10+(s[j]-'0');            if(num>0&&s[i]=='0') return;//去除诸如‘01’，‘010’等无效ip            if(num==0&&j-i>=1) return;//去除诸如'00'等无效ip            if(num<256)            {                ip+='.';//加上.代表到下一级                dfsRestoreIp(s,ip,count+1,j+1,ret);                ip.erase(ip.end()-1);//回溯到上一级            }            else return;        }    }};