115. Distinct Subsequences

# Hard 太难了

Two-sequence DP problem. It's easy to define distinct[i][j], which means how many distinct ways from s[:i] to t[:j]. But how to compute distinct[i][j] according to distinct[i-1[j], distinct[i][j-1] and distinct[i-1][j-1] is difficult to have an idea.

Solution:

1. Initilize distinct[i][j], set empty row and column. distinct[0][0]=1, from s[i] to NULL is 1, from NULL to t[j] is 0.

2. If s[i] = t[j], then distinct[i][j]=distinct[i-1][j-1]+distinct[i-1][j], think this with drawing.

3. If s[i] != t[j], then distinct[i][j]=distinct[i-1][j-1].

4. Return distinct[len(s)][len(t)].

Python

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        # distinct[i][j], means how many distinct ways can generate from s[:i] to t[:j]
        # initilize distinct[i][j]
        distinct = [[0]*(len(t)+1) for i in range(len(s)+1)]
        
        distinct[0][0] = 1
        for i in range(1, len(s)+1):
            distinct[i][0] = 1
        for j in range(1, len(t)+1):
            distinct[0][j] = 0
            
        for i in range(1, len(s)+1):
            for j in range(1, len(t)+1):
                if s[i-1] == t[j-1]:
                    distinct[i][j] = distinct[i-1][j] + distinct[i-1][j-1]
                else:
                    distinct[i][j] = distinct[i-1][j]

        return distinct[len(s)][len(t)]

Java

class Solution {
    public int numDistinct(String s, String t) {
        int[][] ways = new int[s.length()+1][t.length()+1];
        for(int i = 0; i <= s.length(); i ++)
            ways[i][0] = 1;
        for(int j = 1; j <= t.length(); j ++)
            ways[0][j] = 0;
        
        for(int i = 1; i <= s.length(); i ++)
            for(int j = 1; j <= t.length(); j ++) {
                if(s.charAt(i-1) == t.charAt(j-1))
                    ways[i][j] = ways[i-1][j] + ways[i-1][j-1];
                else
                    ways[i][j] = ways[i-1][j];
            }
        return ways[s.length()][t.length()];
    }
}

distinct[i][j] 与distinct[i][j-1]没有任何关系。

这种题最重要的思维是找二维数组distinct[i][j] 与前面的 distinct[i-1][j], distinct[i][j-1], disintct[i][j] 中的谁有直接关系，并且有什么逻辑联系。