115. Distinct Subsequences

Description

Discussion

Method

(LeetCode)

matrix looks like this:

  S 0123....j
T +----------+
  |1111111111|
0 |0         |
1 |0         |
2 |0         |
. |0         |
. |0         |
i |0         |

From here we can easily fill the whole grid: for each(x, y), we check ifS[x] == T[y]we add the previous item and the previous item in the previous row, otherwise we copy the previous item in the same row. The reason is simple:

• if the current character in S doesn't equal to current character T, then we have the same number of distinct subsequences as we had without the new character.
• if the current character in S equal to the current character T, then the distinct number of subsequences: the number we had before plus the distinct number of subsequences we had with less longer T and less longer S.

class Solution {
public:
    int numDistinct(string s, string t) {
        vector<vector<int>> dp(t.size() + 1, vector<int>(s.size() + 1, 0));

        for(int i = 0; i <= s.size(); ++i) {
            dp[0][i] = 1;
        }

        for(int ti = 1; ti <= t.size(); ++ti) {
            for(int si = 1; si <= s.size(); ++si) {
                if(t[ti-1] == s[si-1]) {
                    dp[ti][si] = dp[ti - 1][si - 1] + dp[ti][si - 1];
                }
                else {
                    dp[ti][si] = dp[ti][si - 1];
                }
            }   
        }

        return dp[t.size()][s.size()];
    }
};