首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。