首页 > 代码库 > LeetCode--Restore IP Addresses

LeetCode--Restore IP Addresses

dfs即可

注意边界情况:

(1)s长度不在4 和 12之间

(2)"010"这种形式是错误的

 1 class Solution { 2 public: 3     vector<string> restoreIpAddresses(string s) { 4         vector<string> res; 5         if(s.length() < 4 || s.length() > 12){ 6             return res; 7         } 8          9         dfs(s,"",res,0);10         return res;11     }12     void dfs(string ip,string tmpres,vector<string> &res,int cnt){13         if(cnt == 3 && isvalid(ip)){14             string tmp = tmpres+ip;15             res.push_back(tmp);16             return;17         }18         for(int i = 1 ; i < 4 && i < ip.length() ; ++i){19             string tmp = ip.substr(0,i);20             if(isvalid(tmp)){21                 dfs(ip.substr(i),tmpres+tmp+".",res,cnt+1);22             }23         }24     }25     bool isvalid(string str){26         if(str.length() <= 0)27             return false;28         int tmp = atoi(str.c_str());29         if(str[0] == 0){30             if(str == "0"){31                 return true;32             }33             else34             {35                 return false;36             }37         }38         if(tmp <= 255 && tmp > 0){39             return true;40         }41         return false;42     }43 };

 

LeetCode--Restore IP Addresses