LeetCode题目115:不同子序列

简介: LeetCode题目115:不同子序列
题目描述

给定一个字符串 s 和一个字符串 t ,计算在 s子序列t 出现的个数。

一个字符串的子序列是指,通过删除一些(也可以不删除)字符而不改变剩余字符的相对位置形成的新字符串。(例如,"ACE""ABCDE" 的一个子序列,而 "AEC" 不是)。

示例:

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

输出:3

解释:有 3 种方法可以生成 “rabbit” 的子序列。

难度分析

这道题目是一个动态规划问题,属于中等偏上难度。

解题算法

方法一:动态规划
解题步骤
  1. 初始化一个 (m+1)x(n+1) 的二维数组 dp,其中 mn 分别是字符串 st 的长度。dp[i][j] 表示 s 的前 i 个字符中包含 t 的前 j 个字符的子序列个数。
  2. 设定初始条件:当 j=0,即 t 为空字符串时,dp[i][0] 都为 1
  3. 遍历字符串st,更新dp表:
  • 如果 s[i-1] == t[j-1],则 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
  • 否则,dp[i][j] = dp[i-1][j]
  1. 返回 dp[m][n]
Python 示例
def numDistinct(s: str, t: str) -> int:
    m, n = len(s), len(t)
    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]
方法二:记忆化递归(优化的 DFS)
解题步骤
  1. 使用递归函数 dfs(i, j) 来表示从 s[i:]t[j:] 开始的子序列匹配个数。
  2. 如果 j == len(t),表示 t 已经被完全匹配,返回 1
  3. 如果 i == len(s)j != len(t),则无法匹配,返回 0
  4. 使用一个记忆化数组 memo 来存储已计算的结果,避免重复计算。
  5. 递归计算两种情况:选择当前 s[i] 或者跳过当前 s[i]
Python 示例
def numDistinct(s: str, t: str) -> int:
    memo = {}
    def dfs(i, j):
        if j == len(t):
            return 1
        if i == len(s):
            return 0
        if (i, j) in memo:
            return memo[(i, j)]
        if s[i] == t[j]:
            memo[(i, j)] = dfs(i + 1, j + 1) + dfs(i + 1, j)
        else:
            memo[(i, j)] = dfs(i + 1, j)
        return memo[(i, j)]
    return dfs(0, 0)
方法三:滚动数组优化的动态规划
Python 示例
def numDistinct(s: str, t: str) -> int:
    m, n = len(s), len(t)
    dp = [0] * (n + 1)
    dp[0] = 1  # 初始化dp数组,任何字符串都包含空字符串的子序列,即空序列本身
    for i in range(1, m + 1):
        # 从后向前遍历,防止覆盖需要的数据
        for j in range(n, 0, -1):
            if s[i - 1] == t[j - 1]:
                dp[j] += dp[j - 1]
    return dp[n]
算法分析

滚动数组技术可以减少动态规划的空间复杂度,只使用一维数组存储中间结果,大大减少了内存的使用。

方法四:空间优化的记忆化递归
解题步骤
  1. 类似于记忆化递归,使用一个一维数组 memo 来代替二维数组,减少空间复杂度。
  2. 根据 t 的长度来初始化 memo
  3. 使用递归方式填充 memo,每次计算后存储结果。
Python 示例
def numDistinct(s: str, t: str) -> int:
    n = len(t)
    memo = [-1] * (n + 1)
    def dfs(i, j):
        if j == n:
            return 1
        if i == len(s):
            return 0
        if memo[j] != -1:
            return memo[j]
        res = 0
        if s[i] == t[j]:
            res = dfs(i + 1, j + 1)
        res += dfs(i + 1, j)
        memo[j] = res
        return res
    return dfs(0, 0)
总结
  • 动态规划是解决此类问题的最直接方法,其时间和空间复杂度均较高。
  • 记忆化递归提供了更灵活的解决方案,适用于解决复杂递归问题,但可能会导致堆栈溢出。
  • 滚动数组空间优化的递归可以显著减少空间复杂度,适用于空间敏感的应用。
应用示例

在文本分析和自然语言处理中,计算字符串的子序列可以帮助理解文本的结构和语义。例如,在关键词匹配、信息检索和语言模型中,这些技术可以用来计算和优化大量文本数据。


欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
25天前
|
C语言
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
11 1
|
10天前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
1月前
|
存储
力扣-2904最短且字典序最小的美丽子序列
力扣-2904最短且字典序最小的美丽子序列
15 1
|
22天前
|
算法 索引
力扣经典150题第二十六题:判断子序列
力扣经典150题第二十六题:判断子序列
9 0
|
1月前
|
容器
【LeetCode刷题】栈和队列题目练习~
【LeetCode刷题】栈和队列题目练习~
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(4)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总
|
1月前
|
存储 算法
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(1)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏