leetcode 刷题 log day55

392. 判断子序列
【思路】

var isSubsequence = function(s, t) {
  let dp = new Array(t.length + 1).fill().map(() => Array(s.length + 1).fill(0));
  
  for (let i = 1; i <= t.length; i++) {
    for (let j = 1; j<= s.length; j++) {
      if (s[j - 1] === t[i - 1]) dp[i][j] = dp[i - 1][j - 1] + 1
      else dp[i][j] = dp[i - 1][j];
    }
  }

  return dp[t.length][s.length] === s.length;
};
1
2
3
4
5
6
7
8
9
10
11
12

115. 不同的子序列
【思路】

var numDistinct = function(s, t) {
  let dp = new Array(s.length + 1).fill().map(() => Array(t.length + 1).fill(0));
  dp[0][0] = 1;

  // 初始化
  for (let i = 0; i <= s.length; i++) {
    dp[i][0] = 1;
  }
  
  for (let i = 1; i <= s.length; i ++) {
    for (let j = 1; j <= t.length; j++) {
      if (s[i - 1] === t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
      else dp[i][j] = dp[i - 1][j];
    }
  }
  return dp[s.length][t.length];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17