代码随想录第55天| 392.判断子序列 ， 115.不同的子序列

**代码随想录第55天 |392.判断子序列、115.不同的子序列**

### **前言**

在本篇文章中，我们将讨论两个经典的算法题目：392.判断子序列和115.不同的子序列。这些问题不仅考察了我们的编程能力，还要求我们对数据结构和算法有深入的理解。

### **392.判断子序列**

**问题描述**

给定两个字符串 `s` 和 `t`，判断 `t` 是否是 `s` 的子序列。

**示例**

* 输入：`s = "abc", t = "ahbgdc"`
* 输出：`True`
*说明：因为 `"ahbgdc"` 是 `"abc"` 的子序列。
* 输入：`s = "axc", t = "ahbgdc"`
* 输出：`False`
*说明：因为 `"ahbgdc"` 不是 `"axc"` 的子序列。

**解决方案**

我们可以使用两个指针来实现这个问题。一个指针 `i` 遍历字符串 `s`,另一个指针 `j` 遍历字符串 `t`。当 `s[i] == t[j]` 时，我们移动 `i` 和 `j` 指针，直到 `j` 到达字符串 `t` 的末尾。

def isSubsequence(s: str, t: str) -> bool:
 i = j =0 while i < len(s) and j < len(t):
 if s[i] == t[j]:
 i +=1 j +=1 return i == len(s)

### **115.不同的子序列**

**问题描述**

给定两个字符串 `s` 和 `t`，返回 `s` 中不同长度的子序列数量。

**示例**

* 输入：`s = "abc", t = ""`
* 输出：`7`
*说明：因为 `"abc"` 的不同长度的子序列有 `"","a","b","c","ab","bc","ac"`,总共7 个。
* 输入：`s = "", t = "abc"`
* 输出：`1`
*说明：因为 `""` 的唯一子序列是 `""`。

**解决方案**

我们可以使用动态规划来实现这个问题。我们维护一个长度为 `len(s) +1` 的数组 `dp`，其中 `dp[i]` 表示 `s[:i]` 的不同长度的子序列数量。

def numDistinctSubseq(self, s: str, t: str) -> int:
 dp = [0] * (len(s) +1)
 dp[0] =1 for i in range(1, len(s) +1):
 for j in range(i, -1, -1):
 if s[j:i] == t:
 dp[i] += dp[j-1]
 elif s[j:i] < t:
 dp[i] += dp[j]
 return dp[-1]

### **总结**

在本篇文章中，我们讨论了两个经典的算法题目：392.判断子序列和115.不同的子序列。我们使用两个指针来实现第一个问题，使用动态规划来实现第二个问题。这些问题不仅考察了我们的编程能力，还要求我们对数据结构和算法有深入的理解。

### **参考**

* [392.判断子序列]( />* [115.不同的子序列](