新博文地址:[leetcode]Restore IP Addresses
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)
For example:
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
还是很经典的DFS,只不过要做出一些剪枝操作,
比如第一字段已经确定,后缀长应该在[3,9],如果不再这个范围可以直接跳过
字段以0开头是不合法的,直接跳过(单个0是合法的)
字段大小超过255是不合法的,直接跳过。
跳过要记得回溯
List<String> result = new ArrayList<String>(); public List<String> restoreIpAddresses(String s) { dfs("", s, 1); return result; } private void dfs(String pre,String s, int frag){//frag表示字段数 if(frag == 4 && s.length() < 4 && Integer.valueOf(s) <= 255 ){ if(s.length() > 1 && s.charAt(0) == '0'){//字段长>1,但是以0开头 return; } String oneCase = pre + "." + s; result.add(oneCase); return; } if(frag != 1){ pre += "."; } for(int i = 0 ; i < 3 && i < s.length(); i++){ String suffix = s.substring(i + 1); String thisFrag = s.substring(0, i + 1); if(suffix.length() <= 3 * (4 - frag) && suffix.length() >= (4-frag) && Integer.valueOf(thisFrag) < 256 ){//由于太长了,我将以0开头的剪枝条件放在里面了。。。 if(thisFrag.length() > 1 && thisFrag.charAt(0)=='0'){ break; } pre += thisFrag; dfs(pre, suffix, frag + 1); pre = pre.substring(0, pre.length() - thisFrag.length());//回溯 } } }
相关推荐
leetcode盒子嵌套 leetcode-text 92.Reverse Linked List II Runtime: 4 ms, faster than 67.04% of C online submissions for Reverse Linked List II. Memory Usage: 6.9 MB, less than 100.00% of C online ...
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
restoreIPAddresses 复原IP地址 threeSum 三数之和 search 搜索旋转排序数组 1. 3. 9. 75. 209. 219. 167. 268. 344. 349. 454. 447. 695. 674. string 字符串 20. 150. linklist 链表 19. 24. 86. 92. 203. 206. ...
leetcode中文版
vs code LeetCode 插件
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
093:Restore IP Addresses 树的遍历问题也可以用这种思想来解释。只不过是特殊的递归而已。(只有两路,不用循环) 题型二:动态规划(要整理搜索和DP的区别,都可以用一个状态转移公式F(n)表示) 053:最大字串...
100个leetCode详细解答
LeetCode 刷题汇总1
LeetCode 选讲1
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
leetcode刷题, 直接用leetcode的分类方式.
LeetCode面试笔试题
leetcode高频面试笔试题150+道,亲身总结。
这份文档列出了leetcode几乎所有题目(大约134题)的分类以及难度指示,是刷leetcode的必备良品。现在leetcode总的题目数已经达到150题,所以有部分题目没有包含在这个文档中,但是——足够了。po主刷leetcode的时候...
LeetCode 刷题笔记