回溯算法-切割问题

回溯算法-切割问题
力扣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代码如下：

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

最后

以上就是风中歌曲为你收集整理的回溯算法-切割问题的全部内容，希望文章能够帮你解决回溯算法-切割问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。