leetcode93_复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

思路：

递归回溯，总共有4段，先生成第一段，再递归生成下一段

	public List<String> restoreIpAddresses(String s) {
		List<String> result = new ArrayList<>();
		// 小于4或者大于12则不可能是IP地址
		if (s.length() < 4 || s.length() > 12)
			return result;

		dfs(result, s, "", 1);
		return result;
	}

	// 总共有4段，先生成第一段，再递归生成下一段
	public void dfs(List<String> result, String s, String temp, int count) {
		if (count == 4 && isValid(s)) { // 达到了4段的时候并且第四段也合法 添加到result中
			result.add(new String(temp + s));
			return;
		}

		// Math.min(4, s.length())后面几位少于4的情况
		for (int i = 1; i < Math.min(4, s.length()); i++) {
			String current = s.substring(0, i);      //[0,i)
			if (isValid(current)) // 如果合法就去  递归剩下的部分(i以及之后的部分)
				dfs(result, s.substring(i), temp + current + ".", count + 1);
		}
	}

	// 判断每一段是否合法
	public boolean isValid(String str) {// 两位以上时不能以0为开头，值不能超过255
		if (str.charAt(0) == '0') // 0开头的话 只能是0 只有一位
			return str.equals("0");

		// 值要大于0 小于等于255
		int num = Integer.parseInt(str);
		return 0 < num && num <= 255;
	}

2.直接循环求解

  //直接使用三重循环   耗时间还短一些
	public List<String> restoreIpAddresses2(String s) {
		List<String> res = new ArrayList<String>();
		int len = s.length();
		for (int i = 1; i < 4 && i < len - 2; i++) {
			for (int j = i + 1; j < i + 4 && j < len - 1; j++) {
				for (int k = j + 1; k < j + 4 && k < len; k++) {
					String s1 = s.substring(0, i),        //[0,i)
							s2 = s.substring(i, j),       //[i,j)
							s3 = s.substring(j, k),       //[j,k)
							s4 = s.substring(k, len);     //至少有k
					if (isValid2(s1) && isValid2(s2)
							&& isValid2(s3) && isValid2(s4)) {
						res.add(s1 + "." + s2 + "." 
							+ s3 + "." + s4);
					}
				}
			}
		}
		return res;
	}
 
	public boolean isValid2(String s) {
		if (s.length() > 3 || s.length() == 0 
			|| (s.charAt(0) == '0' && s.length() > 1) 
			|| Integer.parseInt(s) > 255)
			return false;
		return true;
}