LeetCode 115. Distinct Subsequences

本文主要是介绍LeetCode 115. Distinct Subsequences，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

      r a b b b  i  t

  1 1 1 1 1 1 1 1

r 0 1 1 1 1 1 1 1

a 0 0 1 1 1 1 1 1

b 0 0 0 1 2 3 3 3

b 0 0 0 0 1 3 3 3

i  0 0 0 0 0 0 3 3

t  0 0 0 0 0 0 0 3

dp[i][j] =dp[i][j−1],  s[j] != t[i]

dp[i][j] =dp[i][j−1]+dp[i−1][j−1],  s[j] == t[i]​

 

理解：
dp[i][j]表示s[0:j]和t[0:i]的结果
当s[j] 与 t[i]不相等时，当前结果即为前一轮结果
当两者相等时，当前结果可以分为两个情况：
s[j] 与 t[i] 匹配，此时对应的结果为dp[i - 1][j - 1]
s[j] 不与 t[i] 匹配，此时的结果为dp[i][j - 1]
因此最终的结果为两者的和
举个例子：
先补一行一列，第0行表示当t为空时，都可以匹配，第0列表示当s为空时无法匹配.
 

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

 

这篇关于LeetCode 115. Distinct Subsequences的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---