程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode Distinct Subsequences

LeetCode Distinct Subsequences

編輯:關於C++

LeetCode解題之Distinct Subsequences


原題

給定兩個字符串S和T,求T有多少種從屬於S的子序列的情況。或者說S可以刪除它自己任意個字符,但是不能改變字符的相對位置,那一共有多少種刪法可以使S變為T。

注意點:

刪除任意個字符包括不刪除字符

例子:

輸入: s = “rabbbit”, t = “rabbit”

輸出: 3

解題思路

典型的動態規劃問題,dp[i][j]表示字符串S[:i]和T[:j]的不同子序列數目,如果S[i-1]和T[j-1]不相等,那麼只能在S[:i-1]和T[:j]中匹配,即dp[i][j] = dp[i-1][j];而當S[i-1]和T[j-1]相等時,可以是這兩個字符正好匹配,也可以忽略S[i-1],使T[j-1]在S[:i-1]中匹配,所以dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]。進一步觀察可以將二維數組壓縮為一維,只需要從後往前計算即可。

AC源碼

class Solution(object):
    def numDistinct(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: int
        """
        m = len(s)
        n = len(t)
        dp = [0 for __ in range(n + 1)]
        dp[0] = 1
        for i in range(m):
            for j in range(n - 1, -1, -1):
                if t[j] == s[i]:
                    dp[j + 1] += dp[j]
        return dp[-1]


if __name__ == "__main__":
    assert Solution().numDistinct("rabbbit", "rabbit") == 3
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved