> For the complete documentation index, see [llms.txt](https://imhuay.gitbook.io/studies/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://imhuay.gitbook.io/studies/algorithms/problems/2022/01/niu-ke-0020-zhong-deng-shu-zi-zi-fu-chuan-zhuan-hua-cheng-ip-di-zhi.md).

# 数字字符串转化成IP地址

![last modify](https://img.shields.io/static/v1?label=last%20modify\&message=2022-10-14%2014%3A59%3A33\&color=yellowgreen\&style=flat-square) [![](https://img.shields.io/static/v1?label=\&message=%E4%B8%AD%E7%AD%89\&color=yellow\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/01/pages/R5NyOzkn3qAZy7wCx1pS#中等) [![](https://img.shields.io/static/v1?label=\&message=%E7%89%9B%E5%AE%A2\&color=green\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/01/pages/R5NyOzkn3qAZy7wCx1pS#牛客) [![](https://img.shields.io/static/v1?label=\&message=%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/01/pages/R5NyOzkn3qAZy7wCx1pS#深度优先搜索)

**问题简述**

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

> [数字字符串转化成IP地址\_牛客题霸\_牛客网](https://www.nowcoder.com/practice/ce73540d47374dbe85b3125f57727e1e)

**思路：DFS + 回溯**

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

![](/files/5Cx9oqDCepWVouRRfruS)

<details>

<summary><strong>Python</strong></summary>

```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
```

</details>