C++ 解法, 执行用时: 2ms, 内存消耗: 428KB, 提交时间: 2021-12-04

class Mixture {
public:
    bool chkMixture(string A, int n, string B, int m, string C, int v) {
        // write code here
        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(dp[i-1][j] && (A[i-1]==C[i+j-1]) || (dp[i][j-1]&&(B[j-1]==C[i+j-1]))){
                    dp[i][j]=true;
                }
            }
        }
        return dp[n][m];
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 476KB, 提交时间: 2020-10-31

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