1 题目描述

给定一个仅包含数字的字符串，通过返回所有有效的IP地址组合来还原它。

例子：

输入：

"25525511135"

输出：

["255.255.11.135", "255.255.111.35"]

题目出处：

https://leetcode.com/problems/restore-ip-addresses/

2 解决思路

采用递归算法，require标识所需的数字段。

a）从最左分别取1-3个满足0~255的数字；

b）递归处理剩余字符串，且所需的数字段变为require-1；

c）若require为1，判断是否满足ip段内数字要求，满足返回，不满足返回空数组；

d）将a、b两步所得结果拼接为数组返回。

3 golang实现代码

https://github.com/olzhy/leetcode/blob/master/93_Restore_IP_Addresses/test.go

4 问题

以上算法时间复杂度多少？有更优的方案吗？欢迎留言讨论。

原文：https://leileiluoluo.com/posts/leetcode-restore-ip-addresses.html

本文作者：磊磊落落的博客，原创授权发布