leetcode 115 Distinct Subsequences
z
 2019-03-29 16:44:41  

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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
    ^^^

首先很容易想到一个遍历的算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int numDistinct1(String s, String t) {
      return dfs(s, t, 0);
 	}

  public int dfs(String s, String t, int start) {
      if ("".equals(s)) {
          return 0;
      }
      if ("".equals(t)) {
          return 1;
      }
      int count = 0;
      for (int i=start; i<s.length(); i++) {
          if (s.charAt(i) == t.charAt(0)) {
              count += dfs(s, t.substring(1), i+1); 
          }
      }
      return count;
  }

时间复杂度上面是一个O($n^2$)

其实还可以用动态规划来做。

dp[i][j] 表示 t[0:i]在s[0:j]中出现的次数。那么直接返回dp[t.length()][s.length()]就可以了。

当dp[i][j] 确定后，考虑dp[i][j+1]的情况：

  • 当t[i] != s[j+1]时， 当前的字符不相等，那么t[0:i] 在s[0:j+1]中出现的次数就等于它在s[0:j]中出现的次数。即 dp[i][j+1] = dp[i][j].

  • 当t[i] == s[j+1]时，dp[i][j+1]包含两部分，

    • 在s[0: j]中，t[0: i] 出现的此时，这里是t[0:i]已经出现的次数，即dp[i][j]。

    • 新加入的s[j+1]带来的影响。我们已知了t[0: i-1]在s[0:j]中出现的次数，那么新加入的这个s[j+1]可以和s[0: j]中任意一个t[0:i-1]组成一个新的t[0：i]，所以这里将增加dp[i-1][j]。

      即dp[i][j+1] = dp[i][j] + dp[i-1][j]

      举个例子：

      a d a b e b a
      1 1 1 1 1 1 1 1
      a 0 1 1 2 2 2 2 3
      b 0 0 0 0 ?

      在求?时， a在ada中已经出现了2次，ab在ada中出现了0次，当添加一个b时，在ada中出现的两个a都可以和b组成ab，所以一共有0+2次。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    public int numDistinct(String s, String t) {
           int[][] dp = new int[t.length()+1][s.length()+1];
           for (int i=0; i<=t.length(); i++) {
               for (int j=0; j<=s.length(); j++) {
                   if (i==0) {
                       dp[i][j] = 1;
                   }
                   else if (j == 0) {
                       dp[i][j] = 0;
                   }
                   else if (t.charAt(i-1) == s.charAt(j-1)){
                       dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
                   }
                   else
                       dp[i][j] = dp[i][j-1];
               }
           }
           
           return dp[t.length()][s.length()];
       }

    有一点需要注意的是，dp[0][0] 的值，当s为空的时候，对所有的t都不会有结果，即dp[*][0]看似都应该设置为0， 但是当s[0] = t[0] 时，如果dp[0][0] 为0，那么dp[1][1]不会有值。dp[0][0]必须设置为1.