67593c02fbc42873559dac5ba6984f5a
(难度Medium)Problem 93 Restore IP Addresses(有效ip)

链接

Restore IP Addresses - LeetCode

难度等级

Medium

题干

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

题意

给定一串数字,它可能代表一个有效的ip。要求它能表示的所有ip地址的集合

样例

Example:

**Input:** “25525511135”
**Output:** [“255.255.11.135”, “255.255.111.35”]

题解

拿到这道题我的第一反应就是LeetCode出题人新意的匮乏,类似的题目我们好像已经做过不少了。

我们有一系列数据和数据合法的判断条件,想要找到满足某种要求的答案,应该怎么做?

和我们置身在一个迷宫里,知道迷宫允许的行走方法,需要找到迷宫的出口,应该怎么办?

当然是搜索了。

明白了这点,剩下的就水到渠成了。

我们要做什么?找IP,那么IP满足什么条件?位于0~255之间。要找几个?找四个。

当然,我们明确了要找四个ip,完全可以三重循环遍历字符串的三个分割点。但这是取巧的方法,如果我们不知道ip的数量,显然就没办法这样操作了。

搜索的终止条件有两个,一个是ip的数量达到了4个,另一个是所有的字符都派上了用场。

如果搜索没有终止,我们要做的就是搜索下一个ip。显然ip最多只有3位,所以我们只需要最多遍历三种情况。判断这三种情况下能否组合成合法的ip地址,一个合法的ip地址除了小于255之外,还不能有前导零。

最后,我们回溯整个搜索过程即可,更多细节,查看代码

top Created with Sketch.