注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex93 Restore IP Addresses  

2015-05-22 21:59:45|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

明显的深度递归的题目,和ex131几乎一个思路,先构造一个数组和string的长度一样,记录分割的位置。需要注意的是,这里的分割点有且只有三个。分割点之间还需要满足一个条件0~~255之间,另外,这个分割点之间的子串不能是以0开头并且后面还有字符的。有了这个条件限制,就比较好写了。但是提交的代码貌似效率不高,可能递归的过程过于复杂了,有些路径其实可以提前中止的,下次再做这题的时候再好好考虑一下。
代码如下

class Solution {
public:
vector<string> result;
vector<bool>sign;
vector<string> restoreIpAddresses(string s) {
int len = s.size();
if (len <= 3)
return result;
int start = 0,count =3;
for (int i = 0; i < len; i++)
{
sign.push_back(false);
}
traverse(s,start,count);
return result;
}
void traverse(string s, int index,int count)
{
// index 表示下一次切割的起始点
// count 表示还剩余多少次切割
// 深度优先遍历
int len = s.length();
string temp;
int num;
if (count == 0)
{
//剩下的字符全部是最后一个的
temp = s.substr(index,len-index+1);
if (temp[0] == '0'&&temp.size() > 1)
return; //切割点之间的字符串不能是以0开头且长度大于1的串
num = str2int(temp);
string str;
if (num >= 0 && num <= 255)
{
int start = 0;
for (int i = 0; i < len; i++)
{
if (sign[i])
{
str.append(s.substr(start,i-start+1));
str.append(".");
start = i + 1;
}
}
str.append(s.substr(start,len-start));
result.push_back(str);
}
else
{
return;
}
}
else
{
//len - count)是因为后面必须保留 count个切割点
for (int i = index; i < len - count; i++)
{
temp = s.substr(index,i-index+1);
if (temp[0] == '0'&&temp.size() > 1)
continue;
num = str2int(temp);
if (num >= 0 && num <= 255)
{
sign[i] = true;
traverse(s,i+1,count-1);
sign[i] = false; //用完了之后就sign符号就要重置一下,否则容易影响下一次遍历
}
}
}

}
int str2int(string s)
{
int len = s.size();
int res = 0;
for (int i = 0; i < len; i++)
{
res *= 10;
res += s[i] - '0';
}
return res;
}
};



  评论这张
 
阅读(14)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017