当前位置：首页 > article >正文

代码随想录第四十五天

article 2025/2/25 21:45:59

115.不同的子序列

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 10^9 + 7 取模。

示例 1：

输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

示例 2：

输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag

提示：

1 <= s.length, t.length <= 1000
s 和 t 由英文字母组成

思路：

这道题的确有点难，我们首先设置dp[i][j]为s中前i个元素与t前j个元素相匹配的个数，然后我们还要对j=0和i=0的情况进行判断，如果t为空指针那么s可以找到一个与其相匹配的，那么个数就是1，如果s为空，那么个数就为0，最后进行遍历，当满足s[i-1] = t[i-1]时那么dp[i][j]就为前一个个数加上如果前一个数没匹配上的个数，如果不满足就只是没匹配上的个数，最后返回dp[a1][a2]的值就行了。

解答：

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

583.两个字符串的删除操作

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步可以删除任意一个字符串中的一个字符。

示例 1：

输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

示例 2:

输入：word1 = "leetcode", word2 = "etco"
输出：4

提示：

1 <= word1.length, word2.length <= 500
word1 和 word2 只包含小写英文字母

思路：

这道题跟上面差不多，都是对两个字符串进行操作，这道题中的dp[i][j]的含义指的是在第i个元素和第j个元素时需要删除操作需要几步，同样也分为相等和不等两种情况，但是这道题的初始化要注意，当i=0和j=0这两种情况下，相当于有一个空字符串，所以我们需要初始化它们，最后返回dp[a1][a2]就可以得到答案了。

解答：

int minDistance(char* word1, char* word2) {
    int a1 = strlen(word1);
    int a2 = strlen(word2);
    int** dp = calloc(a1+1,sizeof(int*));
    for(int i = 0;i <= a1;i++)
    {
        dp[i] = calloc(a2+1,sizeof(int));
    }
    for(int i = 0;i <= a1;i++)
    {
        dp[i][0] = i;
    }
    for(int j = 0;j <= a2;j++)
    {
        dp[0][j] = j;
    }
    for(int i = 1;i <= a1;i++)
    {
        for(int j = 1;j <= a2;j++)
        {
            if(word1[i-1] == word2[j-1])
            {
                dp[i][j] = dp[i-1][j-1];
            }
            else
            {
                dp[i][j] = fmin(fmin(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+2);
            }
        }
    }
    return dp[a1][a2];
}

72.编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示：

0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成

思路：

我们使用动态规划定义dp[i][j]表示将word1[0...i-1]转化为word2[0...j-1]的最小操作数。初始化时，dp[i][0] = i表示删除操作，dp[0][j] = j表示插入操作。对于每个dp[i][j]，如果word1[i-1]与word2[j-1]相同，dp[i][j] = dp[i-1][j-1]，否则dp[i][j] = fmin(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1。最终dp[a1][a2]就是答案，表示将整个word1转化为word2所需的最小操作次数。

解答：

int minDistance(char* word1, char* word2) {
    int a1 = strlen(word1);
    int a2 = strlen(word2);
    int** dp = calloc(a1+1,sizeof(int*));
    for(int i = 0;i <= a1;i++)
    {
        dp[i] = calloc(a2+1,sizeof(int));
    }
    for(int i = 0;i <= a1;i++)
    {
        dp[i][0] = i;
    }
    for(int j = 0;j <= a2;j++)
    {
        dp[0][j] = j;
    }
    for(int i = 1;i <= a1;i++)
    {
        for(int j = 1;j <= a2;j++)
        {
            if(word1[i-1] == word2[j-1])
            {
                dp[i][j] = dp[i-1][j-1];
            }
            else
            {
                dp[i][j] = fmin(dp[i-1][j-1],fmin(dp[i-1][j],dp[i][j-1]))+1;
            }
        }
    }
    return dp[a1][a2];
}