算法设计与分析-Week15

发表于

Distinct Subsequences

题目描述

Given a string S and a string T, count the number of distinct subsequences of S which equals T.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is a subsequence of “ABCDE” while “AEC” is not).

Example 1:

Input: S = “rabbbit”, T = “rabbit”
Output: 3

Example 2:

Input: S = “babgbag”, T = “bag”
Output: 5

解题思路

本题给出了字符串S和字符串T，要求找出S有多少个子字符串与T相同。
使用二维数组count，count[i][j]表示S的前j个字符组成的字符串有多少个子字符串与T的前i个字符组成的字符串相同，假设n为S字符串的长度，m为T字符串的长度，那么count[m][n]即为所求。具体步骤如下：

  • 首先初始化数组的第一行count[0][j]=1，即当T为空串时，S有一个子字符串（空串）与T相同。
  • 除第一行外，初始化数组的第一列count[i][0]=0，即当S为空串时，没有子字符串与T相同。
  • 依次计算数组的每一行，当比较到S[j-1] == T[i-1]时，count[i][j] = count[i][j-1] + count[i-1][j-1]，否则count[i][j] = count[i][j-1]。这是因为当S的当前字符与T的当前字符不相同时，我们并没有得到新的字符因此数量与前面相等；当S的当前字符与T的当前字符相同时，可从下列表格得出规律。

以样例1为例：

Ø r a b b b i t
Ø 1 1 1 1 1 1 1
r 0 1 1 1 1 1 1
a 0 0 1 1 1 1 1
b 0 0 0 1 2 3 3
b 0 0 0 0 1 3 3
i 0 0 0 0 0 3 3
t 0 0 0 0 0 0 3

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int numDistinct(string s, string t) {
        int n = s.length();
        int m = t.length();
        vector<vector<int>> count(m + 1, vector<int>(n + 1, 0));
        for(int i = 0; i < n + 1; i++) {
            count[0][i] = 1;
        }
        for(int i = 1; i < m + 1; i++) {
            for(int j = 1; j < n + 1; j++) {
                if(s[j - 1] == t[i - 1]) {
                    count[i][j] = count[i][j-1] + count[i-1][j-1];
                }
                else {
                    count[i][j] = count[i][j-1];
                }
            }
        }
        return count[m][n];
    }
};
0%