数字字符串转化成IP地址

问题简述

给定只包含数字的字符串，将该字符串转化成 IP 地址的形式，返回所有可能的情况。
例如：给出的字符串为"25525522135",
返回：["255.255.22.135", "255.255.221.35"]

数字字符串转化成IP地址_牛客题霸_牛客网

思路：DFS + 回溯

• 相当于构建一颗三叉树；

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return string字符串一维数组
#
class Solution:
    def restoreIpAddresses(self , s: str) -> List[str]:
        # write code here
        
        ret = []
        
        def valid(x):
            """验证函数"""
            if not x:  # 非空
                return False
            if x.startswith('0') and len(x) > 1:  # 存在前缀 0
                return False
            return int(x) <= 255
        
        def dfs(k, depth, tmp):
            if depth == 3:  # 到第三层的时候，直接判断所有剩余字符
                if valid(s[k:]):
                    tmp.append(s[k:])
                    ret.append('.'.join(tmp))
                    tmp.pop()  # 这里也要回溯
                return
            
            for i in range(1, 4):
                sub = s[k: k + i]
                if valid(sub):
                    tmp.append(sub)
                    dfs(k + i, depth + 1, tmp)
                    tmp.pop()
        
        dfs(0, 0, [])
        return ret