【一天一道Leetcode】回文字符串-最少分割次数

看那个码农

共 2852字,需浏览 6分钟

 ·

2021-03-14 18:36


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



01


题目描述


题目描述:


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


返回符合要求的最少分割次数


示例:

输入:s = "aab"
输出:1
解释:只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

输入:s = "a"
输出:0
解释:不需要分割,s本身就是回文字符串

输入:s = "ab"
输出:1
解释:在ab之间切割一次,ab分别构成一个回文字符串




02


方法和思路


根据题意可知,

需要返回所有结果个数

 


若字符串s为回文数,则返回0,

表示当前字串不需要分割

我们可以初始化当前字串最小分割次数res=Max


float("inf")
#正无穷

float("-inf")
#负无穷


定义遍历结束索引i,遍历区间[1,N+1)

N为字符串长度

s[0,⋯,i−1]为回文串:


res=min(res,minCut(s[i,⋯,n−1])+1)。
解释:始终保存最小的切割次数。

最后返回res






因为本题可能会涉及到大量的比较,为了提供代码运行效率,较少运行时间,我们引入装饰器。

functools.lru_cache()


functools.lru_cache()是一个装饰器,为函数提供缓存功能。在函数下次以相同参数调用时,可以直接返回上一次的结果。大大降低代码运行时间。


我们可以用生成第n个斐波纳契数的过程,对比使用该装饰器的时间消耗:

斐波那契数列指的是这样一个数列:
数列从第3项开始,每一项都等于前两项之和。
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
144, 233,377,610,987,1597,2584,4181,
6765,10946,17711,28657,46368........


不用装饰器时候的代码:

import time
def fibonacci(n):
    """斐波那契函数"""
    if n < 2:
        return n
    return fibonacci(n - 2) + fibonacci(n - 1)

if __name__ == '__main__':
    stime = time.time()
    print(fibonacci(30))
#斐波那契函数的第30个数字
    print("total time is %.3fs" % (time.time() - stime))
#代码计算时间消耗


此时输出为:
832040
total time is 0.374s


用装饰器时候的代码:

import time
import functools
@functools.lru_cache(None)

def fibonacci(n):
    """斐波那契函数"""
    if n < 2:
        return n
    return fibonacci(n - 2) + fibonacci(n - 1)

if __name__ == '__main__':
    stime = time.time()
    print(fibonacci(30))
#斐波那契函数的第30个数字
    print("total time is %.3fs" % (time.time() - stime))
#代码计算时间消耗


此时输出为:
832040
total time is 0.000s





我们用代码解答本题为:

import functools
class Solution:
    @functools.lru_cache(None)
    def minCut(self, s: str) -> int:
        if s==s[::-1]:
            return 0
        res=float("inf")
        for i in range(1,len(s)+1):
            if s[:i]==s[:i][::-1]:
                res=min(self.minCut(s[i:])+1,res)
        return res




往期回顾

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


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


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


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


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


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



☆ END ☆

你与世界

只差一个

公众号

浏览 60
点赞
评论
收藏
分享

手机扫一扫分享

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

手机扫一扫分享

分享
举报