思路：
回溯+剪枝
遍历字符串，先计算第一网段，分别取1 2 3位数字，并组合判断是否符合IP规范，
若符合跳至下一网段，并且索引start挪位，temp+本网段值+“.”
递归
List<String> l = new ArrayList<>(); public List<String> restoreIpAddresses(String s) { if(s.length()<4 || s.length() > 12){return l;} //1 表示第几个网段 0表示从字符串s哪一位开始算 “”表示追加的IP dfs(s,1,0,""); return l; } private void dfs(String s, int part,int start, String temp) { if(part == 4){ if(isIP(s.substring(start))){ l.add(temp+s.substring(start)); } return; } for (int i = 1; i < 4 && start+i<s.length(); i++) { String t = s.substring(start,start+i); if(isIP(t)){ dfs(s,part+1,start+i,temp+t+"."); } } } private static boolean isIP(String substring) { if (substring.length() > 3) { return false; } if (substring.startsWith("0")) { return "0".equals(substring); } else { return Integer.valueOf(substring) <= 255; } }
