115. Distinct Subsequences
https://leetcode.com/problems/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).
It's guaranteed the answer fits on a 32-bit signed integer.
Example 1:
Input: S ="rabbbit", T ="rabbit" Output: 3Explanation: 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: 5Explanation: 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^^^
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int numDistinct(String s, String t) { | |
| Integer[][] memo = new Integer[s.length()][t.length()]; | |
| return dfs(s, t, 0, 0, memo); | |
| } | |
| private int dfs(String s, String t, int i, int j, Integer[][] memo) { | |
| // End of target => found a match => return 1 | |
| if (j == t.length()) { | |
| return 1; | |
| } | |
| // End of source, and not end of target => no match => return 0; | |
| if (i == s.length()) { | |
| return 0; | |
| } | |
| if (memo[i][j] != null) { | |
| return memo[i][j]; | |
| } | |
| int ans = 0; | |
| // advance on the source regardless | |
| ans = dfs(s, t, i + 1, j, memo); | |
| // If chars match, advance on the target | |
| if (s.charAt(i) == t.charAt(j)) { | |
| ans += dfs(s, t, i + 1, j + 1, memo); | |
| } | |
| memo[i][j] = ans; | |
| return ans; | |
| } | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int numDistinct(String s, String t) { | |
| return dfs(s, t, 0, 0); | |
| } | |
| private int dfs(String s, String t, int i, int j) { | |
| // End of target => found a match => return 1 | |
| if (j == t.length()) { | |
| return 1; | |
| } | |
| // End of source, and not end of target => no match => return 0; | |
| if (i == s.length()) { | |
| return 0; | |
| } | |
| int ans = 0; | |
| // advance on the source regardless | |
| ans = dfs(s, t, i + 1, j); | |
| // If chars match, advance on the target | |
| if (s.charAt(i) == t.charAt(j)) { | |
| ans += dfs(s, t, i + 1, j + 1); | |
| } | |
| return ans; | |
| } | |
| } |
