回溯算法-切割问题

104 阅读 0 评论 69 点赞

我是靠谱客的博主风中歌曲，这篇文章主要介绍回溯算法-切割问题，现在分享给大家，希望可以做个参考。

回溯算法-切割问题
力扣131题
同样地按照回溯三部曲进行代码编写：
回溯三步曲：
1.递归函数参数和返回值
2.确定终止条件
3.单层递归逻辑
1.递归函数参数和返回值
void backtracking(nums,start_index,result,path)
2.确认终止条件
该题的终止条件为叶子节点恰为空结点，此时判断条件可以转化为
if (start_index==nums.size):
result.append(path);
return;
3.单层递归逻辑
for (i=start_index;i<nums.size;i++)
{
if nums[start_index:i+1]是回文串：
{
path.push(nums[i])；
backtracking(nums,i+1,result,path)
path.pop();
}
else:
{
continiue;//结束此次循环
}
}

python代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        if len(s)==0:
            return
        result = []
        path = []
        self.backtracking(s,0,result,path)
        return result
    
    def backtracking(self,s,start_index,result,path):
        if start_index == len(s):
            result.append(path[:])
            return
        for i in range(start_index,len(s)):
            if not self.IsHuiwen(s[start_index:i+1]):
                continue
            path.append(s[start_index:i+1])
            self.backtracking(s,i+1,result,path)
            path.pop()
    def IsHuiwen(self,s):
        l = 0
        r = len(s)-1
        while l<r:
            if s[l]!=s[r]:
                return False
            l += 1
            r -= 1
        return True