392. 判斷子序列

• 思路
  • example
  • 不連續(xù)
  • t字符串可刪除字符 （s不可刪除）
  • 空字符串是非空字符串的子序列

dp[i][j]: s[0,...,i-1]是否為t[0,...,j-1]的子序列
需要注意 初始化

• 復(fù)雜度. 時(shí)間：, 空間:

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        m, n = len(s), len(t)
        dp =[[False]*(n+1) for _ in range(m+1)]
        for j in range(n+1):
            dp[0][j] = True # t = 'ab', s = '', ans = True
        for i in range(1, m+1):
            for j in range(1, n+1):
                if s[i-1] == t[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = dp[i][j-1] # not involving dp[i-1][j]
        return dp[m][n]

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        m, n = len(s), len(t)  
        if m > n:
            return False  
        dp = [[False for _ in range(n+1)] for _ in range(m+1)]
        for j in range(n+1):
            dp[0][j] = True  
        for i in range(1, m+1):
            for j in range(1, n+1):
                if s[i-1] == t[j-1]:
                    dp[i][j] = dp[i-1][j-1] 
                else:
                    dp[i][j] = dp[i][j-1] 
        return dp[m][n]

• 另一種寫法

dp[i][j]: s[0,...,i-1], t[0,...,j-1] 相同子序列的長度 （相同子序列一定以s[i-1]結(jié)尾, 但不一定包括t[j-1]）

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        m, n = len(s), len(t)
        dp =[[0]*(n+1) for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if s[i-1] == t[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = dp[i][j-1] # not involving dp[i-1][j]
        return dp[m][n] == len(s)

• 也可以用 滑窗

TBA

• 進(jìn)階： 如何處理大量的s串？
  • 類似KMP匹配 next 數(shù)組 (t串)

t = 'xyadbe'
如果 s = 'ab'
遍歷s，nxt指針在t移動(dòng)
nxt[0]['a'] = 2
nxt[3]['b'] = 4
如果 s = 'ac'
nxt[0]['a'] = 2
nxt[3]['c'] = 6 (越界，說明t的2th位置之后不出現(xiàn)'c'這個(gè)字符)
所以nxt[i][j]: 字符串t中ith以后j對(duì)應(yīng)的字符第一次出現(xiàn)的位置 （貪心）
nxt數(shù)組用DP思路 (倒序）

• 注意初始化

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        m, n = len(s), len(t)
        nxt = [[n for _ in range(26)] for _ in range(n+1)]
        for i in range(n-1, -1, -1):
            for j in range(26):
                if ord(t[i]) - ord('a') == j:
                    nxt[i][j] = i 
                else:
                    nxt[i][j] = nxt[i+1][j] 
        i = 0
        for ch in s:
            if nxt[i][ord(ch) - ord('a')] == n: # 在t中，從start開始找不到字符s[i]
                return False 
            else:
                i = nxt[i][ord(ch) - ord('a')] + 1 # t: 下一次從這個(gè)位置開始匹配
        return True  

115. 不同的子序列

• 思路
  • example
  • 如果要求連續(xù)子序列，用KMP

dp[i][j]: s[0,...,i-1]的子序列中 t[0,...,j-1]出現(xiàn)的個(gè)數(shù)
當(dāng)s[i-1] == t[j-]時(shí)，分兩種情況：使用s[i-1] vs 不使用s[i-1]
注意初始化

• 復(fù)雜度. 時(shí)間：O(mn), 空間: O(mn)

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
        for i in range(m+1):
            dp[i][0] = 1
        for i in range(1, m+1):
            for j in range(1, n+1):
                if s[i-1] == t[j-1]:
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
                    #          使用s[i-1]       不使用s[i-1]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[m][n]

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)  
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]  
        for i in range(m+1):
            dp[i][0] = 1
        for i in range(1, m+1):
            for j in range(1, n+1):
                if s[i-1] == t[j-1]:
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j] 
                else:
                    dp[i][j] = dp[i-1][j] 
        return dp[m][n]