文章目录
- 93. 复原 IP 地址
- 思路
- 回溯三部曲
- 判断子串是否合法
- 总结
93. 复原 IP 地址
93. 复原 IP 地址
有效 IP
地址 正好由四个整数(每个整数位于 0
到 255
之间组成,且不能含有前导 0
),整数之间用'.'
分隔。
- 例如:
"0.1.2.201"
和"192.168.1.1"
是 有效 IP 地址,但是"0.011.255.245"
、"192.168.1.312"
和"192.168@1.1"
是 无效 IP 地址。
给定一个只包含数字的字符串s
,用以表示一个 IP
地址,返回所有可能的有效 IP
地址,这些地址可以通过在 s
中插入 '.'
来形成。你 不能
重新排序或删除 s
中的任何数字。你可以按 任何
顺序返回答案。
示例 1:
输入:s = "25525511135"
输出:["255.255.11.135","255.255.111.35"]
示例 2:
输入:s = "0000"
输出:["0.0.0.0"]
示例 3:
输入:s = "101023"
输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
-
提示:
-
1 <= s.length <= 20
-
s 仅由数字组成
思路
做这道题目之前,最好先把131.分割回文串 这个做了。
这道题目相信大家刚看的时候,应该会一脸茫然。
其实只要意识到这是切割问题,切割问题就可以使用回溯搜索法把所有可能性搜出来
,和刚做过的131.分割回文串 就十分类似了。
切割问题可以抽象为树型结构,如图(注意,因为分支过多,所以很多分支都省略了,主要是图形示意一下帮助理解,不是完整的图):
回溯三部曲
1.递归参数
在131.分割回文串
中我们就提到切割问题类似组合问题。
res
和path
分别收集最终结果集和当前路径情况。
startIndex
一定是需要的,因为不能重复分割,需要记录下一层递归分割的起始位置。
所以代码如下:
func backtracking(s string,res *[][]string,path *[]string,startIndex int){}
2.递归终止条件
切割到最后则可以返回了,然后本题明确要求只会分成4
段,所以如果切割线切到最后位置,路径中刚好保存的是4
段,则可以作为一个有效结果。
代码如下:
// 切割到末尾时,需要终止递归
// 根据是否刚好切分为了四段,将当前path加入到最终结果中if startIndex >= len(s) {if len(*path) == 4 {pathStr := strings.Join(*path,".")*res = append(*res,pathStr)}return }
3.单层搜索的逻辑
在131.分割回文串 中已经讲过在循环遍历中如何截取子串。
在for i := startIndex; i < len(s); i++
循环中 [startIndex, i](左闭右闭)
这个区间就是截取的子串,需要判断这个子串是否合法。
如果合法就可以添加到当前路径中。
如果不合法就结束本层循环,如图中剪掉的分支:
然后就是递归和回溯的过程:
递归调用时,下一层递归的startIndex
要从i+1
开始(因为不能重复切割同一个位置),回溯的时候,就将刚刚加入子串删掉就可以了。
代码如下:
for i := startIndex;i < len(s);i++ {str := s[startIndex:i + 1] // 当前切割到的子串if !isValid(str){ // 判断 [startIndex,i] 这个区间的子串是否合法break // 不合法,可以直接结束本层循环}*path = append(*path,str)backtracking(s,res,path,i + 1) // 进行下一层的递归切割*path = (*path)[0:len(*path) - 1] // 回溯
}
注意
:这里有一个点与131.分割回文串
有区别,131.分割回文串
中当前子串不是回文子串时,是continue
跳过本轮循环
,因为本层i
变大切割更长的子串后,子串可能又是合法的回文串了,所以可以继续往后切割。而本题93.复原IP地址
,子串不合法的时候可以直接break
退出本层循环
,因为本层i
变大继续切割更长的子串也一定是不合法的(要么有前导0
,要么大于255
了),当然本题即使使用的是continue
而非break
,也是可以AC
的,只是多了很多次判断罢了。
判断子串是否合法
最后就是在写一个判断段位是否是有效段位了。
主要考虑到如下三点:
- 段位以
0
为开头的数字不合法 - 段位里有非正整数字符不合法(题目表示输入一定都是数字,所以该条我们可以不判断)
- 段位如果大于
255
了不合法
代码如下:
func isValid(str string) bool {// 长度大于0,却含有前导0,不合法if len(str) > 1 && str[0] == '0' { return false}num,_ := strconv.Atoi(str)if num > 255 { // 数字大于255,不合法return false}return true
}
根据回溯算法模板:
func backtracking(参数) {if 终止条件) {存放结果return}for 选择:本层集合中元素(树中节点孩子的数量就是集合的大小) {处理节点backtracking(路径,选择列表) // 递归回溯,撤销处理结果}
}
可以写出如下回溯算法Go
代码:
func restoreIpAddresses(s string) []string {// 和131分割回文串类似if len(s) < 4 {return nil}res := make([]string,0)path := make([]string,0)backtracking(s,&res,&path,0)return res
}func backtracking(s string,res *[]string,path *[]string,startIndex int) {// 切割到末尾时,需要终止递归,根据是否刚好切分为了四段,将当前path加入到最终结果中if startIndex >= len(s) {if len(*path) == 4 {pathStr := strings.Join(*path,".")*res = append(*res,pathStr)}return }for i := startIndex;i < len(s);i++ {str := s[startIndex:i + 1] // 当前切割到的子串if !isValid(str){break // continue也可以,不过break能剪枝更多}*path = append(*path,str)backtracking(s,res,path,i + 1) // 进行下一层的递归切割*path = (*path)[0:len(*path) - 1] // 回溯}
}func isValid(str string) bool {if len(str) > 1 && str[0] == '0' { // 长度大于0,却含有前导0,不合法return false}num,_ := strconv.Atoi(str)if num > 255 { // 数字大于255,不合法return false}return true
}
时间复杂度: O ( 3 4 ) O(3^4) O(34),IP
地址最多包含4
段数字,每段数字最多有3
种可能的分割方式,则搜索树的最大深度为4
,每个节点最多有3
个子节点。
空间复杂度: O ( n ) O(n) O(n)
总结
在131.分割回文串
中我列举的分割字符串的难点,本题都覆盖了。
此外,合法性判断难度大一点,以及增加了剪枝和递归终止时能否收集结果的判断,可以说是131.分割回文串
的加强版。
在本文的树形结构图中,我已经把详细的分析思路都画了出来,相信大家看了之后一定会思路清晰不少!