Description:
Given two string S and T, you need to count the number of T's subsequences appeared in S. The fucking problem description is so confusing.
Input:
String s and t
output:
The number
Analysis:
It's a dynamic processing problem. I drew the dynamic processing of counting the seq numbers and then got the correct formula by guessing? :) Most times I work out the final formula by deducing! Then i back to think it's real sense in the problem.
dp[i][j] represents the number of subsequences in string T (ending before index i) are appeared in string S (ending before index j). So, dp can be processed by the follow formula:
= dp[i][j-1] + dp[i-1][j-1] if s[j] == t[i]
dp[i][j]
= dp[i][j-1] if s[j] != t[i]
BYT:
The fucking input size of test cases in serve are ambiguity! So if you create a 2-dimension array in defined size, you will be in trouble. Dynamic structures like vector will be better!
Code:
class Solution { public: int numDistinct(string s, string t) { if(s.length() == 0 || t.length() == 0) return 0; //int dp[50][10908]; vector<vector<int>> dp(t.length() + 1, vector<int>(s.length() + 1, 0)); dp[0][0] = (t[0] == s[0])?1:0; for(int i = 1; i < s.length(); i ++){ if(s[i] == t[0]) dp[0][i] = dp[0][i - 1] + 1; else dp[0][i] = dp[0][i - 1]; } for(int i = 1; i < t.length(); i ++){ dp[i][i - 1] = 0; for(int j = i; j < s.length(); j ++){ dp[i][j] = (t[i] == s[j])? (dp[i][j - 1] + dp[i - 1][j - 1]):dp[i][j - 1]; } } return dp[t.length() - 1][s.length() - 1]; } };