题目描述
给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。
示例:
输入: "25525511135" 输出: ["255.255.11.135", "255.255.111.35"]
暴力求解思路
1.暴力求解,注意检验转换后的长度即可。
Java代码实现
public List<String> restoreIpAddresses(String s) { List<String> ips = new ArrayList<>(); for (int i = 1; i < 4; i++) { for (int j = 1; j < 4; j++) { for (int k = 1; k < 4; k++) { for (int l = 1; l < 4; l++) { if (i + j + k + l == s.length()) { int a = Integer.parseInt(s.substring(0, i)); int b = Integer.parseInt(s.substring(i, i + j)); int c = Integer.parseInt(s.substring(i + j, i + j + k)); int d = Integer.parseInt(s.substring(i + j + k)); if (a <= 255 && b <= 255 && c <= 255 && d <= 255) { String ip = a +"." + b + "." + c + "." + d; if(ip.length() - 3 == s.length()) ips.add(ip); } } } } } } return ips; }
回溯法Java代码实现
public List<String> restoreIpAddresses(String s) { List<String> ips = new ArrayList<>(); restoreIpAddresses(s,0,0,new StringBuffer(),ips); return ips; } /** * s : 字符串 * point_count: 第几个点 * point_index: 当前位置 * curStr : 当前拼接结果 * res : 结果集 */ private void restoreIpAddresses(String s,int point_count,int point_index,StringBuffer curStr,List<String> res){ //递归结束条件 if(point_count > 3) return; if(point_count == 3){ if(s.substring(point_index).length() <= 3){ int last = Integer.parseInt(s.substring(point_index)); if(last <= 255){ int lastLen = curStr.length(); curStr.append(last); if(curStr.length() == s.length() + 3){ res.add(curStr.toString()); } curStr.delete(lastLen,curStr.length()); } } return; } for (int i = 1; i < 4 && (point_index+i < s.length()); i++) { int cur = Integer.parseInt(s.substring(point_index,point_index+i)); if(cur <= 255){ int lastLen = curStr.length(); curStr.append(cur+"."); restoreIpAddresses(s,point_count+1,point_index+i,curStr,res); curStr.delete(lastLen,curStr.length()); } } }