中级编程通关练习题 #7 – 有效IP地址组合

给定一个字符串里面都是数字,按照IP地址的格式来进行分隔,找出所有合法的点分十进制IP地址组合。

IP地址由32位二进制数组成,为便于使用,常以XXX.XXX.XXX.XXX形式表现,每组XXX代表小于或等于255的10进制数,该表示方法称为点分十进制。 例如 CodeGuru.Academy的IP地址是: 162.241.244.103。更多关于IP地址的信息,可以查看维基百科https://zh.wikipedia.org/wiki/IP%E5%9C%B0%E5%9D%80

输入样例:

“1010235”

输出样例:

[‘1.0.10.235’, ‘1.0.102.35’, ‘10.1.0.235’, ‘10.10.2.35’, ‘10.10.23.5’, ‘10.102.3.5’, ‘101.0.2.35’, ‘101.0.23.5’]

上面的输入样例字符串”1010235″,总共可以分隔为八个不同的有效IP地址。

算法思路:

  • 首先需要定义一个函数来检查一个点分十进制是否是合法的IP地址。
  • 然后可以采用下面两种方法来进行字符串分隔:
    • 方法一:使用递归函数进行深度优先搜索
    • 方法二:多重内嵌for循环来穷举所有的可能,并逐一检查