【左神算法】给定一个数字组成的字符串，返回有多少种合法的 IPV4 组合

小咪咪 2021-11-27 05:30 129阅读 0赞

> **题目：给定一个数字组成的字符串 str，返回有多少种合法的 IPV4 组合。**  
> 举例：  
> str = “245111”，只有一种合法 IPV4 组合：245.1.1.1，所以返回 1
> 
> str = “11111”，所有合法的 IPV4 组合为：  
> 1.1.1.11  
> 1.1.11.1  
> 1.11.1.1  
> 11.1.1.1  
> 所以返回 4
> 
> str = “100111”，所有合法的 IPV4 组合为：  
> 100.1.1.1  
> 所以返回1
> 
> 注意：10.01.1.1，并不合法，因为 IPV4 的部分不会出现 01这样的情况。

分析：IPV4 块不能超过 4 个，对于当前 index 指向的字符 来说，有三种情况

1、index 指向的字符自己作为一块；

2）index 和 index + 1 作为一块 【条件是 index != 0 才行】

3）index 和 index + 1、index + 2 作为一块 【条件是 它们组成的数 要 < 256】

这三种情况下，后面能形成多少有效 ip，三个累加就是当前此 index 及其后面能形成有效 ip 的种类数。

*  ### 递归实现【更好理解】 ###

public class IPV4Num {
    
        public static int getIPV4Num(String str){
            if(str == null || str.length() < 4 || str.length() > 12){
                return 0;
            }
            char[] chars = str.toCharArray();
            return process(chars, 0, 0);
        }
    
        /**
         * 从index位置开始有多少种满足要求的ipv4的划分方式
         * @param chars ：字符数组
         * @param index ：从index位置开始
         * @param parts ：之前已经形成了多少部分(ipv4一共4块)
         * @return
         */
        public static int process(char[] chars, int index, int parts){
            if(parts > 4){
                // basecase1：parts最大值为4
                return 0;
            }
            if(index == chars.length){
                // basecase2：只剩下一个字符数时，只有是parts=4时才是合法的
                return parts == 4 ? 1 : 0;
            }
    
            // 选择1：当前index指向的字符独立成一块
            int res = process(chars, index + 1, parts + 1);
            // 选择2：让index和index+1位置的字符，共同构成一个块
            if(chars[index] == '0' || index == chars.length - 1){
                // 如果当前index指向的字符为0或者到了整个字符串的最后一个字符时，不可能满足选择2这种情况
                return res;
            }
            // 选择3：index、index+1、index+2，三个数组成一个块
            if(index + 2 < chars.length){
                int sum = (chars[index] - '0') * 100 + (chars[index + 1] - '0') * 10 + (chars[index] - '0');
                if(sum < 256){
                    res += process(chars, index + 3, parts + 1);
                }
            }
            return res;
        }
    }

*  ### 动态规划 ###

从递归过程可以看到有两个变量：index 和 parts。利用递归过程，开始填充 dp 表，dp\[0\]\[0\] 就是最终的结果。

public class IPV4Num {
    
        // 动态规划实现
        public static int getIPV4NumDynamic(String str){
            if(str == null || str.length() < 4 || str.length() > 12){
                return 0;
            }
    
            char[] chars = str.toCharArray();
            int[][] dp = new int[chars.length + 1][5];
            for(int i = dp.length - 1, j = 0; j < dp[0].length; j++){
                if(j == 4){
                    dp[i][j] = 1;
                }else{
                    dp[i][j] = 0;
                }
            }
    
            int res = 0;
            // 从上到下、从右往左依次填
            for(int i = dp.length - 2; i >= 0; i--){
                for(int parts = 3; parts >= 0; parts--){
                    res = dp[i + 1][parts + 1];
                    if(chars[i] == '0' || i == chars.length - 1){
                        dp[i][parts] = res;
                        continue;
                    }
                    res += dp[i + 2][parts + 1];
                    if(i + 2 < chars.length){
                        int sum = (chars[i] - '0') * 100 + (chars[i + 1] - '0') * 10 + (chars[i] - '0');
                        if(sum < 256){
                            res += dp[i + 3][parts + 1];
                        }
                    }
                    dp[i][parts] = res;
                }
            }
            return dp[0][0];
        }
    }