C语言算法-解答不同的子序列算法问题的C语言实现

题目描述

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

字符串的一个子序列是指，通过删除一些字符（或不删除）且不干扰剩余字符相对位置所形成的新字符串。例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是。

题目保证答案符合 32 位带符号整数范围。

算法思路

动态规划是解决此类问题的常用方法。我们可以使用一个二维数组 dp，其中 dp[i][j]表示字符串 s 的前 i 个字符中包含字符串 t 的前j 个字符的子序列个数。

状态转移方程为：

• 如果 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]。

代码实现

int numDistinct(char *s, char *t) {
    int sLen = strlen(s);
    int tLen = strlen(t);
    
    int dp[sLen + 1][tLen + 1];
    memset(dp, 0, sizeof(dp));
    
    for (int i = 0; i <= sLen; ++i) {
        dp[i][0] = 1;
    }
    
    for (int i = 1; i <= sLen; ++i) {
        for (int j = 1; j <= tLen; ++j) {
            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[sLen][tLen];
}

算法分析

• 时间复杂度：O(m * n)，其中 m 和 n 分别为字符串 s 和 t 的长度。
• 空间复杂度：O(m * n)，使用了二维数组 dp。

示例和测试

#include <stdio.h>

int main() {
    char s[] = "rabbbit";
    char t[] = "rabbit";
    int result = numDistinct(s, t);
    printf("The number of distinct subsequences is: %d\n", result);
    return 0;
}

输出结果：

The number of distinct subsequences is: 3

总结

本文介绍了使用动态规划算法解决字符串中不同子序列问题。动态规划的核心思想是利用已经计算好的状态来推导新的状态，从而降低问题的复杂度。这种方法在处理字符串问题中非常有效。