https://leetcode.com/problems/distinct-subsequences/
你会得到字串s
和t
,请从字串s
中的所有字母,找出有几种组合能组成字串t
一开始的想法是用回朔法把所有可行的组合找出来,但是时间超过系统要求(Time Limit Exceeded),想法如下
先列出字串s
中所有组成t
所需的字母位置,以example2为例:
{b:[0,2,4]}
、{a:[1,5]}
、{g:[3,6]}
接着,从b挑出一个位置i
、a挑出一个大於i
的位置j
、g挑出一个大於j
的位置k
重复几次找出i, j, k
的动作并组合: [0, 1, 3]、[0, 1, 5]、[0, 5, 6]、[2, 5, 6]、[4, 5, 6]
class Solution:
def numDistinct(self, s: str, t: str) -> int:
s_dict = defaultdict(list)
for i in range(len(s)):
s_dict[s[i]].append(i)
def backtracking(level, previ, memo):
if (level, previ) in memo:
return memo[(level, previ)]
if level == len(t):
return 1
ans = 0
for i in s_dict[t[level]]:
if previ < i:
ans += backtracking(level+1, i, memo)
memo[(level, previ)] = ans
return ans
return backtracking(0, -1, {})
第二个解法则是看别人答案来的,先看看程序码吧
class Solution:
def numDistinct(self, s: str, t: str) -> int:
@cache
def dp(i, j):
if j == len(t):
return 1
if i == len(s):
return 0
if len(s) - i < len(t) - j:
return 0
if s[i] == t[j]:
return dp(i+1, j+1) + dp(i+1, j)
return dp(i+1, j)
return dp(0, 0)
这个方法则是从两个字串的第一个字母开始比对,我们先看看下面这部分,并同样以example2当例子
if s[i] == t[j]:
return dp(i+1, j+1) + dp(i+1, j)
return dp(i+1, j)
return dp(i+1, j+1) + dp(i+1, j)
我们分别来看这两个递回的意思
b
),我们就找下组成字串t
需要的字母(找a
)b
)下面这段也很重要,可以节省很多时间,意思是s
剩下的长度比t
剩下的程度还短的话,就不可能组出t
了
if len(s) - i < len(t) - j:
return 0
最後,@cache
要记得加上去,他是叫你的cache采用LRU策略,没加的话过不了
大家中秋快乐
这篇文章简单介绍一下Sass~ Sass 是什麽 ? Sass是一种CSS预处理器语言(CSS pr...
第八天 各位点进来的朋友,你们好阿 小的不才只能做这个系列的文章,但还是希望分享给点进来的朋友,知道...
Python - 根据输入的英文字母排列出有意义的单词-参考笔记 参考资料 Day26- pytho...
Q: 484开始有点词穷了? A: 写程序还是比写文章有灵感呐.. 继上一篇後,要来为卡片创作出另...
表单标签主要功用是用来收集使用者资料 常用情况 : 注册页面... 主要由 表单域、表单元素、提示文...