首页 > 代码库 > Leetcode: Restore IP addresses

Leetcode: Restore IP addresses

2024-07-23 12:11:06   218人阅读

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)

NP问题。也是采用递归的解法。基本思路就是取出一个合法的数字，作为IP地址的一项，然后递归处理剩下的项。可以想象出一颗树，每个结点有三个可能的分支（因为范围是0-255，所以可以由一位两位或者三位组成）。并且这里树的层数不会超过四层，因为IP地址由四段组成，到了之后我们就没必要再递归下去，可以结束了。这里除了上述的结束条件外，另一个就是字符串读完了。

 1 public class Solution { 2     public List<String> restoreIpAddresses(String s) { 3         ArrayList<String> res = new ArrayList<String>(); 4         if (s == null || s.length() == 0) return res; 5         helper(res, "", s, 1, 0); 6         return res; 7     } 8      9     public void helper(ArrayList<String> res, String item, String s, int level, int index) {10         if (index >= s.length()) return;11         if (level == 4) {12             String st = s.substring(index);13             if (isValid(st)) {14                 String f = String.format("%s.%s", item, st);15                 res.add(f);16             }17             return;18         }19         for (int i=1; i<4&&(index+i<=s.length()); i++) {20             String str = s.substring(index, index+i);21             if (isValid(str)) {22                 if (item.length() == 0) {23                     helper(res, str, s, level+1, index+i);24                 }25                 else {26                     String temp = String.format("%s.%s", item, str);27                     helper(res, temp, s, level+1, index+i);28                 }29             }30         }31     }32     33     public boolean isValid(String str) {34         if (str == null || str.length()>3) return false;35         if (str.charAt(0) == ‘0‘ && str.length()>1) return false;36         int num = Integer.parseInt(str);37         if (num>=0 && num<=255) {38             return true;39         }40         return false;41     }42 }

 

Leetcode: Restore IP addresses


联系
我们