链接

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之外，还不能有前导零。

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