解析数字字符串为IPv4地址

10月15日面试题。

题目

给一个全部数字的字符串，用"."分隔为有效的IPv4地址，返回所有符合IP地址要求的切分结果。
例如：字符串"113201110112"，只能切分为一个有效IP为"113.201.110.112"。

解析

根据IP地址的特征，在原始数字字符串三个位置增加"."即可构成一个IP格式的字符串。

方法一，递归回溯方法

在字符串某个位置点下第一个"."，之后尝试点下第二个"."，然后点下第三个"."，这是需要判断IP是否符合要求，如果符合要求保存结果，否则要回溯第三个"."，去尝试下一个位置点下第三个"."。同样的第二个和第一个"."都需要递归回溯，可以得到最终的结果。

方法二，三重循环依次点下三个"."

易于理解的迭代方法，在三重循环依次点下三个"."，判断IP是否有效，如果是有效的IP地址，记录结果，直到三重循环结束。

代码

方法二的代码实现

public List<String> analyseIPString(String IPStr){
    List<String> res = new LinkedList<>();
    if (null == IPStr){
        return res;
    }
    //如果数字字符串长度小于等于3，或者大于12都一定不符合IP地址规则
    if (IPStr.length() <= 3 || IPStr.length() > 12){
        return res;
    }
    //IP地址每一段，最多3位数。
    //第一重循环，第一段0-3位之间，或者子串长度
    int iLength = Math.min(IPStr.length(), 3);
    for (int i = 0; i < iLength; i++){
        //拆分出第一段
        String fstFrag = IPStr.substring(0, i + 1);
        //如果不符合IP规则，继续尝试拆分第一段
        if (!isIPFragment(fstFrag)){
            continue;
        }
        //第二重循环，第二段从第一段结束起，最多3位
        int jLength = Math.min(IPStr.length(), i + 1 + 3);
        for (int j = i + 1; j < jLength; j++){
            //拆分出第二段
            String secFrag = IPStr.substring(i + 1, j + 1);
            //如果不符合IP规则，继续尝试拆分第二段
            if (!isIPFragment(secFrag)){
                continue;
            }
            //第三重循环，第三段从第二段结束起，最多3位
            int kLength = Math.min(IPStr.length(), j + 1 + 3);
            for (int k = j + 1; k < kLength; k++){
                //拆分出第三段
                String thiFrag = IPStr.substring(j + 1, k + 1);
                //如果不符合IP规则，继续尝试拆分第三段
                if (!isIPFragment(thiFrag)) {
                    continue;
                }
                //并且判断第四段是否符合要求
                String fourFrag = IPStr.substring(k + 1);
                if (!isIPFragment(fourFrag)) {
                    continue;
                }
                //如果符合IP规则，记录在list中
                res.add(fstFrag + "." + secFrag + "." + thiFrag + "." + fourFrag);
            }
        }
    }
    return res;
}
//判断IP地址每段是否符合规则
private boolean isIPFragment(String fragment){
    if (fragment == null || fragment.length() <= 0){
        return false;
    }
    int frag = Integer.parseInt(fragment);
    //如果小于0，或者大于255，无效
    if (frag < 0 || frag > 255){
        return false;
    }
    //如果长度大于1，并且以"0"开头，例如"02"，无效的
    if (fragment.length() > 1 && fragment.startsWith("0")){
        return false;
    }
    return true;
}