[LeetCode]115. Distinct Subsequences

正午 2020-01-12 PM 15℃ 0条

问题描述

给定字符串 S 和 T, 计算 S 有多少子串和 T 相等。

一个字符串的子串是从原字符串删除部分字符之后的字符,子串种字符的顺序和原串一致。(例,"ACE" 是 "ABCDE" 的子串, “AEC”不是)

例子1
Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation:
三个子串分别如下:

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

解法一 动态规划

$ f(i,j) $ 表示字符串 s 的前 j 个字符 和 字符串 t 的 前 i 个字符作为子串的个数

class Solution {
public:
    int numDistinct(string s, string t) {
        const int N = s.size(), M = t.size();
        vector<vector<long long> > dp(M+1, vector<long long>(N+1, 0));
        for(int i = 0; i <= N; i++)
            dp[0][i] = 1;
        for(int i = 1; i <= M; i++)
            dp[i][0] = 0;
        for(int i = 1; i <= M; i++)
            for(int j = i; j <= N; j++) {
                if(t[i-1] == s[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
                }
                else
                    dp[i][j] = dp[i][j-1];
            }
        return dp[M][N];
    }
};
标签: LeetCode

非特殊说明,本博所有文章均为博主原创。

评论