Given a string containing only digits, restore it by returning all possible valid IP address combinations.
Example
Input: “25525511135”
Output: [“255.255.11.135”, “255.255.111.35”]
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
public List<String> (String s) { List<String> result = new ArrayList<>(); restoreIpAddressesHelper(result, new ArrayList<>(), s, 0 , 0 ); return result; } private void restoreIpAddressesHelper (List<String> result, List<String> ip, String s, int idx, int level) { if (level == 4 && idx == s.length()) { result.add(ip.get(0 ) + "." + ip.get(1 ) + "." + ip.get(2 ) + "." + ip.get(3 )); return ; } if (level == 4 || idx == s.length()) return ; for (int i = 1 ; i <= 3 && idx + i <= s.length(); i++) { String str = s.substring(idx, idx + i); if (!isValid(str)) break ; ip.add(str); restoreIpAddressesHelper(result, ip, s, idx + i, level + 1 ); ip.remove(ip.size() - 1 ); } } private boolean isValid (String s) { if (s.length() > 1 && s.charAt(0 ) == '0' ) return false ; int i = Integer.parseInt(s); return i <= 255 && i >= 0 ; }
近期评论