C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2021-01-30

class Mixture {
public:
    bool chkMixture(string A, int n, string B, int m, string C, int v) {
        // write code here
        if(n+m != v) return false;
        if(v == 0) return true;
        vector<vector<bool>> dp(n+1,vector<bool>(m+1,false));
        dp[0][0]=true;
        for(int i = 1; i <= n; i++){
            if(A[i-1] != C[i-1]) break;
            dp[i][0] = true;     
        }
        for(int j = 1; j <= m; j++){
            if(B[j-1] != C[j-1]) break;
            dp[0][j] = true;     
        }
        for(int i=1; i<=n; i++)
        
            for(int j=1; j<=m; j++)
            {
                if((A[i-1]==C[i+j-1]&&dp[i-1][j])||(B[j-1]==C[i+j-1]&&dp[i][j-1]))
                    dp[i][j] = true;
            }
        
        return dp[n][m];
                   
        
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 420KB, 提交时间: 2022-07-31

class Mixture {
public:
    bool ret = false;

    void match(string& A, int n, string& B, int m, string& C, int v) {
        if (v == C.size()) {
            ret = true;
        }
        if (n < A.size() && A[n] == C[v]) {
            match(A,n+1,B,m,C,v+1);
        }
        if (m < B.size() && B[m] == C[v]) {
            match(A, n , B, m+1, C, v + 1);
        }
    }

    bool chkMixture(string A, int n, string B, int m, string C, int v) {
        if (n + m != v) {
            return false;
        }
        match(A, 0, B, 0, C, 0);
        return ret;
    }
};