题解 | #数字字符串转化成IP地址#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return string字符串一维数组
#
class Solution:
    def restoreIpAddresses(self , s: str) -> List[str]:
        # write code here
        n = len(s)
        res = []
        if n < 4 or n > 12:
            return res
        
        def dfs(cur: str, idx: int, count: int) -> None:
            if idx == n and count == 4:
                res.append(cur[:-1])
                return
            
            if n - idx > (4 - count) * 3 or n - idx < 4 - count:
                return
            
            num, i = 0, idx
            while i < idx + 3 and i < n:
                num = num * 10 + int(s[i])
                if num <= 255:
                    cur += s[i]
                    dfs(cur + '.', i + 1, count + 1)
                if num == 0:
                    break
                i += 1
        dfs('', 0, 0)
        return res