【一天一道Leetcode】回文字符串

看那个码农

共 2160字,需浏览 5分钟

 ·

2021-03-14 18:36


本篇推文共计2000个字,阅读时间约3分钟。



01


题目描述


题目描述:

给定一个字符串s,将s分割成一些子串,使每个子串都是回文串。


返回s所有可能的分割方案。


示例:

输入:"aab"
输出:
[
  ["aa","b"
],
  ["a","a","b"]
]




02


方法和思路


根据题意可知,

返回所有可能的结果,而不是结果个数,我们可以使用回溯法。

 

回溯法是采用试错的思想,它尝试用分步的策略去解决一个问题。在分步解决问题的过程中,当它通过尝试,发现现有的分步答案不能得到有效的正确的解答的时候,它将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答再次尝试寻找问题的答案。


回溯法通常用最简单的递归方法来实现,在反复重复上述的步骤后可能出现两种情况:

 

1.找到一个可能存在的正确的答案。

2.在尝试了所有可能的分步后发现该问题没有答案。


注:

回溯法是一种算法思想;

遍历是实现回溯法的编程方法。

 





例如下图所示,即为本文的回溯法思想



我们用指针start尝试着不同位置开始切割字符串,若切出一个回文串,基于新的字符串start,继续往下切,直到start字符串越界

 

每次基于当前start,可以选择不同i,切出start到i的子串,i代表数组的下标,如图字符串aab的012下标。


如上图第一次切割选择了不同i进行切割,

可以切割出a,aa,aab

 

1.对于切割出来的a,此时a为回文字符串,则继续切割剩下的ab字符串。



ab字符串中,可以选择切割成a和ab两条切割道路

-若切a,此时切割出来的a为回文字符串,
则继续切割剩下的b字符串,
此时切割出来的b为回文字符串,
则此时存储该条道路切割得到的[a,a,b]

-若切ab,此时切割出来的ab不为回文字符串,
则跳过该选择,不落入递归,不存储。


2.对于切割出来的aa,此时aa为回文字符串,则继续切割剩下的b字符串。



此时切割出来的b为回文字符串,
则此时存储该条道路切割得到的[aa,b]


3.对于切割出来的aab,此时aab不为回文字符串。



则跳过该选择,不落入递归,不存储。






我们用代码表示为:

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        self.isPalindrome=lambda s:s==s[::-1]
        res=[]
        self.back(s,res,[])
        return res

    def back(self,s,res,path):
        if not s:
            res.append(path)
            return 
        for i in range(1,len(s)+1):
            if self.isPalindrome(s[:i]):
                self.back(s[i:],res,path+[s[:i]])





往期回顾

【年终总结】你好2021,再见2020。


【快速写好毕业论文】你不得不知晓的七个常用文献搜索平台


【秋招纪实录】一篇特别正经的【腾讯】求职经验分享


【一天一道Leetcode】矩阵不可变


【一天一道Leetcode】用栈实现队列


【一天一道Leetcode】套信封问题



☆ END ☆

你与世界

只差一个

公众号

浏览 42
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报