给定一个仅包含数字的字符串,通过返回所有有效的IP地址组合来还原它。
例子:
输入:
"25525511135"
输出:
["255.255.11.135", "255.255.111.35"]
题目出处:
https://leetcode.com/problems/restore-ip-addresses/
采用递归算法,require标识所需的数字段。
a)从最左分别取1-3个满足0~255的数字;
b)递归处理剩余字符串,且所需的数字段变为require-1;
c)若require为1,判断是否满足ip段内数字要求,满足返回,不满足返回空数组;
d)将a、b两步所得结果拼接为数组返回。
https://github.com/olzhy/leetcode/blob/master/93_Restore_IP_Addresses/test.go
以上算法时间复杂度多少?有更优的方案吗?欢迎留言讨论。
原文:https://leileiluoluo.com/posts/leetcode-restore-ip-addresses.html
本文作者:磊磊落落的博客,原创授权发布