正规中国建筑装饰产业网官网_四川建设网有限公司怎么样_磁力天堂torrentkitty_seo设置是什么

LCR 087. 复原 IP 地址

使用回溯法就可以解决问题

class Solution {
public:vector<string> restoreIpAddresses(string s) {vector<string> ans;vector<string> cur;backtrace(s,0,cur,ans);return ans;}void backtrace(string &s,int idx,vector<string> &cur,vector<string> &ans){if(cur.size() == 4 && idx == s.size()){string curS = join(cur);ans.push_back(curS);return;}if(cur.size() > 4 || idx > s.size()){return;}for(int len = 1;len<=3;++len){if(idx+len > s.size()) break;string part  = s.substr(idx,len);if(isValid(part)){cur.push_back(part);backtrace(s,idx+len,cur,ans);cur.pop_back();}}}bool isValid(string s){int num = stoi(s);if(num == 0 && s.size() > 1){return false;}if(num != 0 && s[0] == '0'){return false;}if(num >=0 && num <=255){return true;}return false;}string join(vector<string> cur){string ret = "";for(int i=0;i<cur.size()-1;++i){ret = ret + cur[i] + ".";}ret = ret + cur.back();return ret;}
};