LeetCode解题 Day19

115. Distinct Subsequences

https://leetcode.com/problems/distinct-subsequences/


题目解释

你会得到字串st,请从字串s中的所有字母,找出有几种组合能组成字串t

example

https://i.imgur.com/LGZRRXD.png


解法

  • 今天来不及解,明天补上,预估会用回朔法吧
  • 9/20补上

一开始的想法是用回朔法把所有可行的组合找出来,但是时间超过系统要求(Time Limit Exceeded),想法如下

  1. 先列出字串s中所有组成t所需的字母位置,以example2为例:
    {b:[0,2,4]}{a:[1,5]}{g:[3,6]}

  2. 接着,从b挑出一个位置i、a挑出一个大於i的位置j、g挑出一个大於j的位置k

  3. 重复几次找出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)我们分别来看这两个递回的意思

  1. dp(i+1, j+1): 如果两个字母相同(找到b),我们就找下组成字串t需要的字母(找a)
  2. dp(i+1, j): 就算两个字母相同,我们也当成不需要他,再次去寻找同样目标(找其他位置的b)

下面这段也很重要,可以节省很多时间,意思是s剩下的长度比t剩下的程度还短的话,就不可能组出t

if len(s) - i < len(t) - j:
    return 0

最後,@cache要记得加上去,他是叫你的cache采用LRU策略,没加的话过不了


闲聊

大家中秋快乐/images/emoticon/emoticon61.gif


<<:  Day 19 印章文字

>>:  Day 4 - 资料绑定与模板语法

[Day 04] Sass - 简介

这篇文章简单介绍一下Sass~ Sass 是什麽 ? Sass是一种CSS预处理器语言(CSS pr...

Visual Basic语言和你 SAY HELLO!!

第八天 各位点进来的朋友,你们好阿 小的不才只能做这个系列的文章,但还是希望分享给点进来的朋友,知道...

Python - 根据输入的英文字母排列出有意义的单词-参考笔记

Python - 根据输入的英文字母排列出有意义的单词-参考笔记 参考资料 Day26- pytho...

CSS微动画 - 卡片简约动态效果,翻转是另一种感觉~

Q: 484开始有点词穷了? A: 写程序还是比写文章有灵感呐.. 继上一篇後,要来为卡片创作出另...

Day 04 HTML<表单标签>

表单标签主要功用是用来收集使用者资料 常用情况 : 注册页面... 主要由 表单域、表单元素、提示文...