动态规划

字符串

  • 不同的子序列

    难度：困难

    给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。

    示例 1：
    输入：s = “rabbbit”, t = “rabbit”
    输出：3
    示例 2：
    输入：s = “babgbag”, t = “bag”
    输出：5

  • 方法一

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution:
      def numDistinct(self, s: str, t: str) -> int:
          m = len(s)
          n = len(t)
          if m<n:
              return 0
          dp = [[0]*(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]

    解析

    复杂度分析
    时间复杂度：O(mn)，其中 m 和 n 分别是字符串 s 和 t 的长度。二维数组 dp 有 m+1 行和 n+1 列，需要对 dp 中的每个元素进行计算。
    空间复杂度：O(mn)，其中 m 和 n 分别是字符串 s 和 t 的长度。创建了 m+1 行 n+1 列的二维数组 dp。