【一天一道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
解释:在a和b之间切割一次,a和b分别构成一个回文字符串
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】套信封问题
你与世界
只差一个
公众号
评论