大家好,又见面了,我是全栈君。
字符串的问题真是难。一般递归比較好写代码,一般地归还会超时,并且測试用例特别多。。
这道题刚拿到手时直接慌了,这情况也太多了。后来冷静下来想想,事实上还是比較单纯的。
一个ip地址,肯定是四个整数加三个点构成,四个整数要满足什么呢,0~255嘛,还有呢,就是这四个整数必须正好把原来的字符串给用完。一開始忽略掉的一类測试用类是前面有0但实际这个数不是零的情况。
用什么来穷举呢,或者说穷举的对象是什么呢?当然是要插入的三个点的位置,数的有效范围非常小,因此穷举的范围也非常小,1~3个数位而已,代码一看。就明确是怎么回事了。我最開始的时候想着是把每个小数字用substr存起来,然后最后拼接,这种开销太大了,不建议。
bool isValide(string s, int start, int end){ if(end - start > 3) return false; if(s[start] == '0' && end-start>0) return false; int res = 0; for(int i=start;i<=end;i++) res = res*10+(s[i]-'0'); if(res<0||res>255) return false; return true; } class Solution { public: vector<string> restoreIpAddresses(string s) { vector<string> res; int len = s.length(); if(len<4) return res; string tp(len+3, '#'); for(int i=0;i<3&&i<len-3;i++){ if(!isValide(s, 0, i)) continue; //cout<<i<<" i"<<endl; for(int j=i+1;j<i+4&&j<len-2;j++){ if(!isValide(s, i+1, j)) continue; //cout<<j<<" j"<<endl; for(int k=j+1;k<j+4&&k<len-1;k++){ //cout<<k<<" k"<<endl; if(!(isValide(s, j+1, k)&&isValide(s, k+1, len-1))) continue; //cout<<"**"<<endl; int index = 0, m = 0; while(index<=i) tp[m++] = s[index++]; tp[m++] = '.'; while(index<=j) tp[m++] = s[index++]; tp[m++] = '.'; while(index<=k) tp[m++] = s[index++]; tp[m++] = '.'; while(index<len) tp[m++] = s[index++]; //cout<<tp<<endl; res.push_back(tp); } } } return res; } };
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115321.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...