算法_回溯_分割回文串_回文 回溯算法 google

分割回文串

leetcode链接

1.解法

切割问题也是回溯问题中的一种，它类似于组合问题，但又不完全一样。

对于这道题而言，我们可以先画出它的树图来帮助理解为什么他也是回溯问题：

对于这个例子[a,a,b]而言：

先不考虑回文的问题，只考虑切割[a,a,b]，有多少种切法。

想要切分[a,a,b]。我们可以先切出a，然后就要考虑如何切分[a,b]，然后我们再切出a，就要考虑如何切分[b]，到这里可以看出每切出一个元素，就要考虑相同的问题，所以这是一个递归问题，而且每次切分的集合都是除去当前已经选择的元素所剩的集合，所以我们用一个startindex来控制集合范围。

现在我们考虑回文的问题，如果我们每次切出来的部分是回文的，那么就证明我们可以接着向后进行切分，如果不是回文的，那么后面的情况就不用考虑了。对应图上可以看先切a，然后切ab这种情况。

那么如果每次切出来的部分都是回文的，那么到什么时候终止呢？要当startindex的位置遍历到了字母集合的最后面，即所有字母都切割完了。就可以把当前这种情况存入result中了。

现在可以考虑回溯三部曲了：

1. 首先确定函数头和一些辅助变量：

    result = [] # 存放最终结果
    path = [] # 存放当前结果
   
    def backtracking(startindex,s)
   1
   2
   3
   4

2. 确定递归出口：

    if startindex == len(s):
    	result..append(path)
    	return
   1
   2
   3

3. 确定递归逻辑：

    for i in range(startindex,len(s)):
    	temp = s[startindex:i+1] # 获取当前循环下的切割字符串
    	if temp == temp[::-1]:
    		path.append(temp) # 如果是回文的则存入path中
    	else:
    		continue # 如果不是回文则该次循环不成立，直接进行下一次循环
    	
    	backtracking(i+1,s)
    	path.pop()
   1
   2
   3
   4
   5
   6
   7
   8
   9

完整代码：

def partition(s):
    result = []
    path = []
    length = len(s)

    def backtracking(startindex,s):
        if startindex>=length:
            path1 = path.copy()
            result.append(path1)
            return

        for i in range(startindex,len(s)):
            temp = s[startindex:i+1]

            if temp == temp[::-1]:
                path.append(temp)
            else:
                continue

            backtracking(i+1,s)
            path.pop()

    backtracking(0,s)
    return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3.总结

python

python从右向左切片：

list[列表右端:列表左端-1:-1]

注意这种情况下如果想要从右向左到头，不能写成list[列表右端