iT邦幫忙

2021 iThome 鐵人賽

DAY 19
0
自我挑戰組

每日LeetCode解題紀錄系列 第 19

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


上一篇
LeetCode解題 Day18
下一篇
LeetCode解題 Day20
系列文
每日LeetCode解題紀錄30

尚未有邦友留言

立即登入留言