链接
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之外,还不能有前导零。
最后,我们回溯整个搜索过程即可,更多细节,查看代码
链接
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之外,还不能有前导零。
最后,我们回溯整个搜索过程即可,更多细节,查看代码
链接
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之外,还不能有前导零。
最后,我们回溯整个搜索过程即可,更多细节,查看代码