IP那个LeetCode上做过,我记得最出乎意料的一点是以0开头的,只能是0,其他判断都还比较简单,DFS+DP很容易解决,代码是我LeetCode上的解决办法,问题略有不同,原问题返回所有IP,这里我size了一下
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String line = in.nextLine();
System.out.println(restoreIpAddresses(line).size());
}
public static List<String> restoreIpAddresses(String s) {
List<String> ret = new ArrayList<>();
if (s == null || s.length() < 4 || s.length() > 32)
return ret;
findIP(s, 0, 3, new Stack<>(), ret);
return ret;
}
public static void findIP(String s, int start, int part, Stack<String> stack, List<String> ret) {
if (part == -1) {
ret.add(toIP(stack));
return;
}
for (int i = start + 1, count = 0; count < 3 && i <= s.length(); i++, count++) {
if (s.length() - i >= part && s.length() - i <= 3 * part && Integer.parseInt(s.substring(start, i)) < 256) {
stack.push(s.substring(start, i));
findIP(s, i, part - 1, stack, ret);
stack.pop();
}
if (s.charAt(start) == '0')
break;
}
}
public static String toIP(Stack<String> stack) {
StringBuilder ret = new StringBuilder();
for (String s : stack) {
ret.append(s).append(".");
}
return ret.deleteCharAt(ret.length() - 1).toString();
}
}