力扣算法题—093复原IP地址

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

示例:

输入: "25525511135"

输出: ["255.255.11.135", "255.255.111.35"]

 //暴力搜索

 //一共分为4组

 //每组数据不超过三位

 class Solution {

 public:

     vector<string> restoreIpAddresses(string s) {

         vector<string>res;

         for(int a = ; a<;++a)

             for(int b=;b<;++b)

                 for(int c =;c<;++c)

                     for(int d=;d<;++d)

                         if (a + b + c + d == s.size()) {

                             int A = stoi(s.substr(, a));//取子串并转为数组

                             int B = stoi(s.substr(a, b));

                             int C = stoi(s.substr(a+b, c));

                             int D = stoi(s.substr(a+b+c, d));

                             if (A <=  && B <=  && C <=  && D <= ) {

                                 string str = to_string(A) + "." + to_string(B) + "." + to_string(C) + "." + to_string(D);

                                 if (str.size() == (s.size() + ))//去除010这种组合

                                     res.push_back(str);

                             }

                         }

         return res;

     }

 };

 //使用递归

 class Solution {

 public:

     vector<string> restoreIpAddresses(string s) {

         vector<string>res;

         helper(s, , "",res);

         return res;

     }

     void helper(string s, int n, string out, vector<string>&res) {

         if (n == ) {

             if (s.empty())res.push_back(out);//全部组合4组IP完毕

         }

         else {

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

                 if (s.size() < k)break;

                 int val = stoi(s.substr(, k));//取子串转化为数字

                 if (val >  || k != to_string(val).size())//当数字大于255或出现010，不满足

                     continue;

                 helper(s.substr(k), n + , out + s.substr(, k) + (n ==  ? "" : "."), res);

             }

         }

     }

 };

力扣算法题—093复原IP地址的相关教程结束。