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();
    }
}