模版题-动态规划-判断子序列
- 版权声明：本站原创文章，于2026-06-03，由 管理员 发表。
- 转载请注明： 模版题-动态规划-判断子序列 | CodeGarden
```python
class Solution:
# 给定字符串s和t，判断s是否为t的子序列。
# 字符串的一个子序列是原始字符串删除一些（也可以不删除）
# 字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
# 进阶：
# 如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，
# 你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
def isSubsequence(self, s: str, t: str) -> bool:
# 判断s是否为t的子序列
# 即,t中每个元素通过删除或保留能够产生s
# t中每个元素两种状态:保留;删除
# 枚举t中每个状态的排列组合,判断是否存在s
# 这种通过枚举状态判断结果的问题,一般都考虑通过动态规划优化。
ns, nt = len( s ), len( t )
if ns == 0: return True
if ns > nt: return False
# dp[ i ][ j ]表示以s[i]结尾的字符串是否是以t[j]结尾的字符串的子序列
dp = [ [ False for _ in range( nt + 1 ) ] for _ in range( ns + 1 ) ]
# 初始化: s[ -1 ]相当于字符串为空串
for j in range( nt + 1 ): dp[ 0 ][ j ] = True
for i in range( 1, ns + 1 ):
for j in range( 1, nt + 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[ ns ][ nt ]
```