首页 > 代码库 > leetcode-distinct sequences
leetcode-distinct sequences
Solution: when see question about two strings , DP should be considered first.
We can abstract this question to calculate appear times for string T with length i in string S with length j, which can be represented by numbers[i][j], then through observation and thinking , we can know for numbers[i][j] it should at least equal the numbers[i][j-1] and if T.charAt(i)==S.charAt(j) , numbers[i][j] should also be add numbers[i-1][j-1]
1 class Solution 2 { 3 public: 4 int numDistinct(string S, string T) { 5 int sLen = S.length(); int tLen = T.length(); 6 vector<vector<int>> dp(sLen+1,vector<int>(tLen+1));//dp[i][j]表示对应S前i个和T前j个字符的子问题。 7 for (int i = 0; i <= sLen; i++) dp[i][0] = 1; 8 for (int i = 1; i <= sLen; i++) 9 {10 for (int j = 1; j <= tLen; j++)11 {12 if (S[i - 1] == T[j - 1])13 {14 dp[i][j] = dp[i - 1][j] + dp[i-1][j-1];15 }16 else17 {18 dp[i][j] = dp[i-1][j];19 }20 }21 }22 return dp[sLen][tLen];23 }24 25 };26 int main()27 {28 Solution s;29 string strS("b");30 string strT("a");31 cout << s.numDistinct(strS, strT) << endl;32 return 0;33 }
http://rleetcode.blogspot.com/2014/01/distinct-subsequences-java.html
leetcode-distinct sequences
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。