首页 > 代码库 > [leetcode]Restore IP Addresses
[leetcode]Restore IP Addresses
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)
算法思路：
一般而言，求出所有**，全部**，都是用穷尽法，DFS即其中一种搜索方法，相比BFS而言，代码简洁，可读性强
1 public class Solution { 2 public List<String> restoreIpAddresses(String s) { 3 List<String> result = new ArrayList<String>(); 4 if(s == null || s.length() < 4) return result; 5 dfs(result,new StringBuilder(),s,0); 6 return result; 7 } 8 9 private void dfs(List<String> result,StringBuilder pre,String suffix,int n){10 if(n > 3 || (n == 3 && ( suffix.length() == 0 || suffix.length() > 3 || Integer.valueOf(suffix) > 255 || (suffix.length() > 1 && suffix.charAt(0) == ‘0‘))))return;11 if(n == 3 && suffix.length() <= 3){12 result.add(pre + suffix);13 return;14 }15 for(int i = 0; i < Math.min(3, suffix.length()); i++){16 StringBuilder oldPre = new StringBuilder(pre);17 String tem = suffix.substring(0, i + 1);18 int tem2Int = Integer.valueOf(tem);19 if(tem2Int > 255 || (tem.length() > 1 && tem2Int < 10)) return;20 pre = pre.append(tem).append(‘.‘);21 n++;22 dfs(result, pre, suffix.substring(i + 1), n);23 pre = oldPre;24 n--;25 }26 }27 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。