首页 > 其他分享 >【LeetCode】131. 分割回文串

【LeetCode】131. 分割回文串

时间:2023-12-26 13:33:42浏览次数:38  
标签:分割 示例 res dfs 131 path LeetCode 回文

题目

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

 

示例 1:

输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]
示例 2:

输入:s = "a"
输出:[["a"]]
 

提示:

1 <= s.length <= 16
s 仅由小写英文字母组成

思路:
dfs
往后遍历每个位置

代码

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res, path, n = [], [], len(s)
        def dfs(i):
            if i == n:
                res.append(path.copy())
                return
            for j in range(i, n):
                t = s[i: j + 1]
                if t == t[::-1]:
                    path.append(t)
                    dfs(j + 1)
                    path.pop()
        dfs(0)
        return res

标签:分割,示例,res,dfs,131,path,LeetCode,回文
From: https://www.cnblogs.com/basilicata/p/17927939.html

相关文章

  • 【LeetCode】17. 电话号码的字母组合
    链接:https://leetcode.cn/problems/letter-combinations-of-a-phone-number/思路:利用深度优先遍历遍历两个空间第一个空间是digits,命名为space1第二个空间是digits的每一位自身的空间,命名为space2关键是遍历完每一个space2之后,如何转到space1的下一个space2中代码classS......
  • 【LeetCode】39. 组合总和
    题目给你一个无重复元素的整数数组candidates和一个目标整数target,找出candidates中可以使数字和为目标数target的所有不同组合,并以列表形式返回。你可以按任意顺序返回这些组合。candidates中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数......
  • 【LeetCode】79. 单词搜索
    链接:https://leetcode.cn/problems/word-search/思路:利用深度优先遍历深度优先遍历一般流程:判断当前是否符合要求若符合要求,则看更深一层是否符合要求最后逐层向上返回代码classSolution:defexist(self,board:List[List[str]],word:str)->bool:m,......
  • Leetcode LCP 02. 分式化简
    https://leetcode.cn/problems/deep-dark-fraction/description/有一个同学在学习分式。他需要将一个连分数化成最简分数,你能帮助他吗?连分数是形如上图的分式。在本题中,所有系数都是大于等于0的整数。输入的cont代表连分数的系数(cont[0]代表上图的a0,以此类推)。返回一个长度......
  • Leetcode LCP 14. 切分数组
    https://leetcode.cn/problems/qie-fen-shu-zu/description/给定一个整数数组nums,小李想将nums切割成若干个非空子数组,使得每个子数组最左边的数和最右边的数的最大公约数大于1。为了减少他的工作量,请求出最少可以切成多少个子数组。示例1:输入:nums=[2,3,3,2,3,3]......
  • 『LeetCode』9. 回文数 Palindrome Number
    题目描述给你一个整数x,如果x是一个回文整数,返回true;否则,返回false。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。例如,121是回文,而123不是。示例1:输入:x=121输出:true示例2:输入:x=-121输出:false解释:从左向右读,为-121。从右向左读,为121-。因此......
  • LeetCode-17 电话号码的字母组合
    LeetCode-17电话号码的字母组合给定一个仅包含数字2-9的字符串,返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下(与电话按键相同)。注意1不对应任何字母。示例1:输入:digits="23"输出:["ad","ae","af","bd","be","bf","cd","ce&qu......
  • LeetCode-15 三数之和
    LeetCode-15三数之和给你一个整数数组nums,判断是否存在三元组[nums[i],nums[j],nums[k]]满足i!=j、i!=k且j!=k,同时还满足nums[i]+nums[j]+nums[k]==0。请你返回所有和为0且不重复的三元组。**注意:**答案中不可以包含重复的三元组。示例1:输入:nums=[-1......
  • 『LeetCode』8. 字符串转换整数 (atoi) String to Integer (atoi)
    题目描述请你来实现一个myAtoi(strings)函数,使其能将字符串转换成一个32位有符号整数(类似C/C++中的atoi函数)。函数myAtoi(strings)的算法如下:读入字符串并丢弃无用的前导空格检查下一个字符(假设还未到字符末尾)为正还是负号,读取该字符(如果有)。确定最终结果是负数还是正......
  • 2023-2024-1 20231319《计算机基础与程序设计》第十三周学习总结
    2023-2024-120231300《计算机基础与程序设计》第十三周学习总结作业信息这个作业属于哪个课程2023-2024-1-计算机基础与程序设计这个作业要求在哪里2023-2024-1计算机基础与程序设计第x周作业这个作业的目标《C语言程序设计》第12章教材学习内容总结从基本......