链接:93. 复原 IP 地址 - 力扣(LeetCode)
这道题需要对字符串进行操作,我选择了三层循环,其实还可以递归。
我在循环时进行了剪枝,比如一些情况直接跳出循环。
我的代码:
class Solution {
public:vector<string> restoreIpAddresses(string s) {vector<string> ans;if(s.size()>12||s.size()<4) return ans;string t;for(int i1=0;i1<3;i1++){string q3=s.substr(0,i1+1);t+=s[i1]; t+='.';if((q3.size()==3&&q3>"255")||(q3>"0"&&q3<"1")) break;int l1=t.size();for(int i2=i1+1;i2<i1+4;i2++){if(i2>=s.size()) break;string q2=s.substr(i1+1,i2-i1);t+=s[i2]; t+='.';if((q2.size()==3&&q2>"255")||(q2>"0"&&q2<"1")) break;int l2=t.size();for(int i3=i2+1;i3<i2+4;i3++){if(i3>=s.size()-1) break;string q1=s.substr(i2+1,i3-i2);t+=s[i3]; t+='.';if((q1.size()==3&&q1>"255")||(q1>"0"&&q1<"1")) break;string t4=s.substr(i3+1,s.size()-i3-1);if(t4.size()>3||(t4.size()==3&&t4>"255")||(t4>"0"&&t4<"1")) t.erase(t.size()-1);else{t+=t4;ans.push_back(t);t.erase(t.size()-t4.size()-1);}}t.erase(l2-1);}t.erase(l1-1);}return ans;}
};