HJ90 合法IP 题解

by 限时烟花

抽丝剥茧

题目说明比较简单，就是输入一个字符串，判断其是否符合IP地址的规范。 IPv4地址的要求：

1. 一共四段
2. 每段之间以“.”隔开
3. 每段的数字只能是0~255之间的数字

化繁为简

最简单的想法是直接将整个输入用“.”分割，那么每一段就可以用相同的规则进行判断。 做完题之后说一下踩到的坑：

1. 输入的每一段有可能为空
2. 输入的内容可能存在非法的符号，比如+-之类的
3. 输入的每一段有可能是以0开头的（这对于IP地址是非法的）

码上行动

经过一些坑，从一开始的版本对没有考虑到的情况进行了一些纠正。

1. 首先要判断每一个num是不是为空；
2. 然后使用正则匹配掉了以0开始或者其他非数字字符的情况；
3. 设置了flag来对四位的情况做统计

import re


while True:
    try:
        s = input().split('.')
        if len(s) != 4:
            print('NO')
            continue
        else:
            flag = True
            for num in s:
                if num:
                    pattern = '^(0+)([0-9]+)|[^0-9]'
                    if re.match(pattern, num):
                        print('NO')
                        flag = False
                        break
                    if 0 <= int(num) <= 255:
                        continue
                    else:
                        print('NO')
                        flag = False
                        break
                else:
                    print('NO')
                    flag = False
                    break
            if flag:
                print('YES')
    except:
        break

例题图示

心有成算

空间复杂度：使用了常数个临时变量，故空间复杂度为：$O(1)O(1)$

时间复杂度：正则匹配的复杂度为$O(n)O(n)$，而split之后的的s的长度是常数级别的，故时间复杂度为$O(n)O(n)$

另辟蹊径

也可以完全基于正则表达式进行

import re


while True:
    try:
        s = input() + '.'
        pattern = "^((25[0-5]|2[0-4]\\d|1\\d\\d|[1-9]\\d|\\d)\.){4}$"
        if re.match(pattern, s):
            print('YES')
        else:
            print('NO')
    except:
        break

空间复杂度：使用了n长变量故空间复杂度为：$O(n)O(n)$

时间复杂度：正则匹配的复杂度为$O(n^5)O(n^5)$，故时间复杂度为$O(n^5)O(n^5)$