LeetCode-115. Distinct Subsequences

LeetCode-115. 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 ​​Explanation: As shown below, there are 3 ways you can generate "rabbit" from S. (The caret symbol ^ means the chosen letters) ​​rabbbit​​​ ^^^^ ^^ ​​​rabbbit​​​ ^^ ^^^^ ​​​rabbbit​​ ^^^ ^^^

Example 2:

Input: S = "babgbag", T = "bag"​​Output: 5 ​​Explanation: As shown below, there are 5 ways you can generate "bag" from S. (The caret symbol ^ means the chosen letters) ​​babgbag​​​ ^^ ^ ​​​babgbag​​​ ^^ ^ ​​​babgbag​​​ ^ ^^ ​​​babgbag​​​ ^ ^^ ​​​babgbag​​ ^^^

题解：

动态规划问题，如果两个字符相等，寻找前面所有已经匹配的前缀串数量并相加，否则就不变。

class Solution {public: int numDistinct(string s, string t) { int n = t.length(), m = s.length(); vector> dp(n + 1, vector(m + 1, 0)); for (int i = 0; i <= m; i++) { dp[0][i] = 1; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; 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[n][m]; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。