算法题--解析IP地址
2020-04-26 本文已影响0人
岁月如歌2020
image.png
0. 链接
1. 题目
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
A valid IP address consists of exactly four integers (each integer is between 0 and 255) separated by single points.
Example:
Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
2. 思路1:回溯法
- 利用回溯法, 逐个确定每个数字, 直至得到合法结果; 如果中途失败, 则回溯到上一个选择并撤销
- 为了增加速度,可以提前排除掉后续数字数不够或超出的选择
3. 代码
# coding:utf8
from typing import List
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
options = [1, 2, 3]
def seek(i, n, result, results):
if n == 0:
if len(result) == 4 and i == 0:
results.add('.'.join([str(x) for x in result]))
else:
for option in options:
if i < option:
continue
value = s[i - option: i]
if option > 1 and value[0] == '0':
continue
if option == 3 and value > '255':
continue
if n > 1 and (i - option < n - 1 or i - option > (n - 1) * 3):
continue
result.insert(0, value)
seek(i - option, n - 1, result, results)
result.pop(0)
rtn_list = set()
seek(len(s), 4, list(), rtn_list)
return list(rtn_list)
def my_test(solution, s):
print('input: {}, output: {}'.format(s, solution.restoreIpAddresses(s)))
solution = Solution()
my_test(solution, '25525511135')
my_test(solution, '0000')
my_test(solution, '010010')
输出结果
input: 25525511135, output: ['255.255.11.135', '255.255.111.35']
input: 0000, output: ['0.0.0.0']
input: 010010, output: ['0.10.0.10', '0.100.1.0']