频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
[LeetCode]Restore IP Addresses
2015-01-26 14:06:11         来源:大力拜  
收藏   我要投稿

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)


深搜+回溯+剪枝


public class Solution {
	List res = new ArrayList(); 
	List list = new ArrayList<>(); 
	public List restoreIpAddresses(String s) {
		if(s.length()<4||s.length()>12) return res;
		help(s,list,0);
		return res;
	}
	
	private void help(String s,List list,int start){
		if((s.length()-start)>(4-list.size())*3) return;
		if(list.size()==4){
			res.add(list.get(0)+"."+list.get(1)+"."+list.get(2)+"."+list.get(3));
		}
		for(int j=1;j<=3&&start+j<=s.length();j++){
			String str;
			if(list.size()==3){
				str = s.substring(start);
			}else{
				str = s.substring(start,start+j);
			}
			int it = -1;
			if(!(str.length()>=2&&str.charAt(0)=='0')) it = Integer.parseInt(str);
			if(it>=0&&it<=255){
				list.add(it);
				help(s,list,start+j);
				list.remove(list.size()-1);
			}
		}
	}
}


点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:Codeforces Round #287 (Div. 2)A,B,C,D,E
下一篇:poj1830--开关问题(高斯消元问题1)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站