- 代码随想录之回溯系列分割问题算法
- 1.分割回文串
- 1.1回溯
- 2.复原IP地址
- 2.1暴力解法
- 2.2回溯(无path)
- 2.3回溯(有全局变量path)
- 2.4回溯(有局部变量path )
var result [][]string
var path []string // 放已经回文的子串
func partition(s string) [][]string {
result = [][]string{}
path = []string{}
backtrack(s, 0)
return result
}
func backtrack(s string, startIndex int) {
// 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
//写startIndex == len(s)也可以
if startIndex >= len(s) {
result = append(result, append([]string{}, path...))
return
}
for i := startIndex; i < len(s); i++ {
// 是回文子串
if isPartition(s, startIndex, i) {
// 获取[startIndex,i]在s中的子串
path = append(path, s[startIndex:i+1])
} else {
continue // 不是回文，跳过
}
backtrack(s, i+1) // 寻找i+1为起始位置的子串
path = path[:len(path)-1] // 回溯过程，弹出本次已经填在的子串
}
}
//判断是否为回文
func isPartition(s string, startIndex, end int) bool {
left := startIndex
right := end
for left < right {
if s[left] != s[right] {
return false
}
//移动左右指针
left++
right--
}
return true
}
本题这涉及到两个关键问题：
切割问题，有不同的切割方式
判断回文
切割问题来说，这种题目，想用for循环暴力解法，可能都不那么容易写出来，所以要换一种暴力的方式，就是回溯，切割问题类似组合问题
例如对于字符串abcdef：
组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中在选组第三个…。
切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段…。
所以切割问题，也可以抽象为一棵树形结构，如图：
递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。
此时可以发现，切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。
回溯三部曲
1.递归函数参数：
全局变量数组path存放切割后回文的子串，二维数组result存放结果集。 （这两个参数可以放到函数参数里）
本题递归函数参数还需要startIndex，因为切割过的地方，不能重复切割，和组合问题也是保持一致的。
在回溯算法：求“组合总和”中我们深入探讨了组合问题什么时候需要startIndex，什么时候不需要startIndex。
代码如下：
var result [][]string
var path []string // 放已经回文的子串
func backtrack(s string, startIndex int) {}
2.递归函数终止条件
从树形结构的图中可以看出：切割线切到了字符串最后面，说明找到了一种切割方法，此时就是本层递归的终止终止条件。
那么在代码里什么是切割线呢？
在处理组合问题的时候，递归参数需要传入startIndex，表示下一轮递归遍历的起始位置，这个startIndex就是切割线。
所以终止条件代码如下：
// 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
if startIndex >= len(s) {
result = append(result, append([]string{}, path...))
return
}
3.单层搜索的逻辑
来看看在递归循环，中如何截取子串呢？
在for i := startIndex; i < len(s); i++ {}循环中，我们 定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。
首先判断这个子串是不是回文，如果是回文，就加入在 path中，path用来记录切割过的回文子串。
注意切割过的位置，不能重复切割，所以，backtracking(s, i + 1); 传入下一层的起始位置为i + 1。
代码如下：
for i := startIndex; i < len(s); i++ {
// 是回文子串
if isPartition(s, startIndex, i) {
// 获取[startIndex,i]在s中的子串
path = append(path, s[startIndex:i+1])
} else {
continue // 不是回文，跳过
}
backtrack(s, i+1) // 寻找i+1为起始位置的子串
path = path[:len(path)-1] // 回溯过程，弹出本次已经填在的子串
}
这道题目在leetcode上是中等，但可以说是hard的题目了，但是代码其实就是按照模板的样子来的。
那么难究竟难在什么地方呢？
我列出如下几个难点：
1.切割问题可以抽象为组合问题
2.如何模拟那些切割线
3.切割问题中递归如何终止
4.在递归循环中如何截取子串
5.如何判断回文
本题主要卡在了第一个难点上：就是不知道如何切割，甚至知道要用回溯法，也不知道如何用。也就是没有体会到按照求组合问题的套路就可以解决切割。
如果意识到这一点，算是重大突破了。接下来就可以对着模板照葫芦画瓢。
但接下来如何模拟切割线，如何终止，如何截取子串，其实都不好想，最后判断回文算是最简单的了。
关于模拟切割线，其实就是index是上一层已经确定了的分割线，i是这一层试图寻找的新分割线
除了这些难点，本题还有细节，例如：切割过的地方不能重复切割所以递归函数需要传入i + 1。
所以本题应该是一个道hard题目了。
131.分割回文串
2.复原IP地址 2.1暴力解法func judgeNumber(num string) bool {
if len(num) > 1 && num[0] == '0' {
return false
}
result := 0
for i := 0; i < len(num); i++ {
result = 10*result + int(num[i]-'0')
}
if result > 255 {
return false
}
return true
}
func restoreIpAddresses(s string) []string {
if len(s) < 4 || len(s) > 12 {
return nil
}
var result []string
for i := 1; i < 4 && i < len(s)-2; i++ {
for j := i + 1; j < i+4 && j < len(s)-1; j++ {
for k := j + 1; k < j+4 && k < len(s); k++ {
if judgeNumber(s[0:i]) && judgeNumber(s[i:j]) && judgeNumber(s[j:k]) && judgeNumber(s[k:]) {
result = append(result, strings.Join([]string{s[0:i], s[i:j], s[j:k], s[k:]}, "."))
}
}
}
}
return result
}
2.2回溯(无path)
var res []string
func restoreIpAddresses(s string) []string {
res = []string{}
if len(s) > 12 {
return res
}
backTracking(s, 0, 0)
return res
}
func backTracking(s string, startIndex int, pointNum int) {
if pointNum == 3 {
if isValid(s, startIndex, len(s)-1) {
res = append(res, s)
}
return
}
for i := startIndex; i < len(s); i++ {
if isValid(s, startIndex, i) {
s = s[:i+1]+"." + s[i+1:]
pointNum++
backTracking(s, i+2, pointNum)
pointNum--
s = s[:i+1]+ s[i+2:]
} else {
break
}
}
}
// 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
func isValid(s string, startIndex, end int) bool {
if startIndex > end {
return false
}
if s[startIndex] == '0' && startIndex != end { // 0开头的数字不合法
return false
}
num := 0
for i := startIndex; i <= end; i++ {
if s[i] > '9' || s[i] < '0' { // 遇到非数字字符不合法
return false
}
num = num*10 + int(s[i]-'0') //num每一次进行累加
if num > 255 {
return false
}
}
return true
}
只要意识到这是切割问题，切割问题就可以使用回溯搜索法把所有可能性搜出来，和刚做过的"分割回文串"就十分类似了。
切割问题可以抽象为树型结构，如图：
1.递归参数
在"分割回文串"中我们就提到切割问题类似组合问题。
startIndex一定是需要的，因为不能重复分割，记录下一层递归分割的起始位置。
本题我们还需要一个变量pointNum，记录添加逗点的数量。
所以代码如下：
2.递归归终止条件
终止条件和”分割回文串情况“就不同了，本题明确要求只会分成4段，所以不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件。
pointNum表示逗点数量，pointNum为3说明字符串分成了4段了。
然后验证一下第四段是否合法，如果合法就加入到结果集里
代码如下：
3.单层搜索的逻辑
在"分割回文串"中已经讲过在循环遍历中如何截取子串。
在for int i = startIndex; i < s.size(); i++{}循环中 [startIndex, i] 这个区间就是截取的子串，需要判断这个子串是否合法。
如果合法就在字符串后面加上符号.表示已经分割。
如果不合法就结束本层循环，如图中剪掉的分支：
然后就是递归和回溯的过程：
递归调用时，下一层递归的startIndex要从i+2开始（因为需要在字符串中加入了分隔符.），同时记录分割符的数量pointNum 要 +1。
回溯的时候，就将刚刚加入的分隔符. 删掉就可以了，pointNum也要-1。
代码如下：
最后就是在写一个判断段位是否是有效段位了。
主要考虑到如下三点：
1)段位以0为开头的数字不合法
2)段位里有非正整数字符不合法
3)段位如果大于255了不合法
2.3回溯(有全局变量path)在"分割回文串"中我列举的分割字符串的难点，本题都覆盖了。
而且本题还需要操作字符串添加逗号作为分隔符，并验证区间的合法性。
可以说是"分割回文串"的加强版。
var res, path []string
func restoreIpAddresses(s string) []string {
res = []string{}
path =[]string{}//这个不能去掉
backTracking(s, 0)
return res
}
func backTracking(s string, startIndex int) {
//终止条件
if startIndex == len(s) && len(path) == 4 {
tmpIpString:=path[0]+"."+path[1]+"."+path[2]+"."+path[3]
res=append(res,tmpIpString)
return //这个return可以不写
}
for i := startIndex; i < len(s); i++ {
//要设置个length保证path的纯洁
length := len(path)
path = append(path, s[startIndex:i+1])
if i-startIndex+1 <= 3 && len(path) <= 4 && isNormalIp(s, startIndex, i) {
backTracking(s, i+1)
} else {
return
}
path = path[:length]
}
}
func isNormalIp(s string, startIndex, end int) bool {
checkInt, _ := strconv.Atoi(s[startIndex : end+1])
if end-startIndex+1 > 1 && s[startIndex] == '0' {
return false
}
if checkInt > 255 {
return false
}
return true
}
var res, path []string
func restoreIpAddresses(s string) []string {
res = []string{}
path = []string{}
backTracking(s, 0)
return res
}
func backTracking(s string, startIndex int) {
if startIndex == len(s) && len(path) == 4 {
tmpIpString := path[0] + "." + path[1] + "." + path[2] + "." + path[3]
res = append(res, tmpIpString)
return
}
for i := startIndex; i < len(s); i++ {
length := len(path)
path = append(path, s[startIndex:i+1])
if i-startIndex+1 <= 3 && len(path) <= 4 && isValid(s, startIndex, i) {
backTracking(s, i+1)
} else {
return
}
path = path[:length]
}
}
//这与isNormalIp是一模一样的
func isValid(s string, startIndex, end int) bool {
if startIndex > end {
return false
}
if s[startIndex] == '0' && startIndex != end {
return false
}
num := 0
for i := startIndex; i <= end; i++ {
if s[i] > '9' || s[i] < '0' {
return false
}
num = num*10 + int(s[i]-'0')
if num > 255 {
return false
}
}
return true
}
//以下是错误的方式
var res, path []string
func restoreIpAddresses(s string) []string {
res =[]string{}
backTracking(s, 0)
return res
}
func backTracking(s string, startIndex int) {
//终止条件
if startIndex == len(s) && len(path) == 4 {
res = append(res,(append([]string{},path...))... )
}
for i := startIndex; i < len(s); i++ {
//处理
path = append(path, s[startIndex:i+1])
if i-startIndex+1 <= 3 && len(path) <= 4 && isNormalIp(s, startIndex, i) {
//递归
backTracking(s, i+1)
} else { //如果首尾超过了3个，或路径多余4个，或前导为0，或大于255，直接回退
return
}
//回溯
path = path[:len(path)-1]
}
}
func isNormalIp(s string, startIndex, end int) bool {
checkInt, _ := strconv.Atoi(s[startIndex : end+1])
if end-startIndex+1 > 1 && s[startIndex] == '0' { //对于前导 0的IP（特别注意s[startIndex]=='0'的判断，不应该写成s[startIndex]==0，因为s截取出来不是数字）
return false
}
if checkInt > 255 {
return false
}
return true
}
//以下是错误的方式
var res, path []string
func restoreIpAddresses(s string) []string {
res = []string{}
backTracking(s, 0)
return res
}
func backTracking(s string, startIndex int) {
//终止条件
if startIndex == len(s) && len(path) == 4 {
tmpIpString:=path[0]+"."+path[1]+"."+path[2]+"."+path[3]
res=append(res,tmpIpString)
return
}
for i := startIndex; i < len(s); i++ {
//要设置个length保证path的纯洁
length := len(path)
path = append(path, s[startIndex:i+1])
if i-startIndex+1 <= 3 && len(path) <= 4 && isNormalIp(s, startIndex, i) {
backTracking(s, i+1)
} else {
return
}
path = path[:length]
}
}
func isNormalIp(s string, startIndex, end int) bool {
checkInt, _ := strconv.Atoi(s[startIndex : end+1])
if end-startIndex+1 > 1 && s[startIndex] == '0' {
return false
}
if checkInt > 255 {
return false
}
return true
}
//以下是错误的方式
var res, path []string
func restoreIpAddresses(s string) []string {
res = []string{}
path =[]string{}
backTracking(s, 0)
return res
}
func backTracking(s string, startIndex int) {
//终止条件
if startIndex == len(s) && len(path) == 4 {
res = append(res, append([]string{}, path...)...)//不能这样写
return
}
for i := startIndex; i < len(s); i++ {
//要设置个length保证path的纯洁
length := len(path)
path = append(path, s[startIndex:i+1])
if i-startIndex+1 <= 3 && len(path) <= 4 && isNormalIp(s, startIndex, i) {
backTracking(s, i+1)
} else {
return
}
path = path[:length]
}
}
func isNormalIp(s string, startIndex, end int) bool {
checkInt, _ := strconv.Atoi(s[startIndex : end+1])
if end-startIndex+1 > 1 && s[startIndex] == '0' {
return false
}
if checkInt > 255 {
return false
}
return true
}
2.4回溯(有局部变量path )
func restoreIpAddresses(s string) []string {
var res,path []string
if len(s) < 4 || len(s) > 12 {
return nil
}
backTracking(s,path,0,&res)
return res
}
func backTracking(s string,path []string,startIndex int,res *[]string){
//终止条件
if startIndex==len(s)&&len(path)==4{
tmpIpString:=path[0]+"."+path[1]+"."+path[2]+"."+path[3]
*res=append(*res,tmpIpString)
// return //这个return写不写都可以通过
}
for i:=startIndex;i
//处理
path=append(path,s[startIndex:i+1])
if i-startIndex+1<=3&&len(path)<=4&&isNormalIp(s,startIndex,i){
//递归
backTracking(s,path,i+1,res)
}else {//如果首尾超过了3个，或路径多余4个，或前导为0，或大于255，直接回退
return
}
//回溯
path=path[:len(path)-1]
}
}
func isNormalIp(s string,startIndex,end int)bool{
checkInt,_:=strconv.Atoi(s[startIndex:end+1])
if end-startIndex+1>1&&s[startIndex]=='0'{//对于前导 0的IP（特别注意s[startIndex]=='0'的判断，不应该写成s[startIndex]==0，因为s截取出来不是数字）
return false
}
if checkInt>255{
return false
}
return true
}
93.复原IP地址
