算法题--解析IP地址

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']

4. 结果

image.png