解题思路

这是一个字符串交错组成问题，可以使用动态规划求解。关键点：

  1. 动态规划定义：

    • 表示 的前 个字符和 的前 个字符是否能交错组成 的前 个字符
    • 范围：， 范围：

  2. 状态转移：

    • 如果 ：
    • 如果 ：

  3. 边界条件：

    • 第一行：只用 串匹配
    • 第一列：只用 串匹配

代码

class Mixture {
public:
    bool chkMixture(string A, int n, string B, int m, string C, int v) {
        if(n + m != v) return false;
        
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        dp[0][0] = 1;
        
        // 初始化第一列
        for(int i = 1; i <= n; i++) {
            if(A[i-1] == C[i-1]) {
                dp[i][0] = dp[i-1][0];
            }
        }
        
        // 初始化第一行
        for(int j = 1; j <= m; j++) {
            if(B[j-1] == C[j-1]) {
                dp[0][j] = dp[0][j-1];
            }
        }
        
        // 填充dp表
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(A[i-1] == C[i+j-1]) {
                    dp[i][j] |= dp[i-1][j];
                }
                if(B[j-1] == C[i+j-1]) {
                    dp[i][j] |= dp[i][j-1];
                }
            }
        }
        
        return dp[n][m];
    }
};

public class Mixture {
    public boolean chkMixture(String A, int n, String B, int m, String C, int v) {
        if(n + m != v) return false;
        
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;
        
        // 初始化第一列
        for(int i = 1; i <= n; i++) {
            if(A.charAt(i-1) == C.charAt(i-1)) {
                dp[i][0] = dp[i-1][0];
            }
        }
        
        // 初始化第一行
        for(int j = 1; j <= m; j++) {
            if(B.charAt(j-1) == C.charAt(j-1)) {
                dp[0][j] = dp[0][j-1];
            }
        }
        
        // 填充dp表
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(A.charAt(i-1) == C.charAt(i+j-1)) {
                    dp[i][j] |= dp[i-1][j];
                }
                if(B.charAt(j-1) == C.charAt(i+j-1)) {
                    dp[i][j] |= dp[i][j-1];
                }
            }
        }
        
        return dp[n][m];
    }
}

# -*- coding:utf-8 -*-
# -*- coding:utf-8 -*-

class Mixture:
    def chkMixture(self, A, n, B, m, C, v):
        # Check length first
        if n + m != v:
            print("Length not match")
            return False
            
        dp = [[False] * (m + 1) for _ in xrange(n + 1)]
        dp[0][0] = True
        
        # Initialize first column
        for i in xrange(1, n + 1):
            if A[i-1] == C[i-1]:
                dp[i][0] = dp[i-1][0]
                print("Match A[%d]=%s with C[%d]=%s" % (i-1, A[i-1], i-1, C[i-1]))
        
        # Initialize first row
        for j in xrange(1, m + 1):
            if B[j-1] == C[j-1]:
                dp[0][j] = dp[0][j-1]
                print("Match B[%d]=%s with C[%d]=%s" % (j-1, B[j-1], j-1, C[j-1]))
        
        # Fill dp table
        for i in xrange(1, n + 1):
            for j in xrange(1, m + 1):
                if A[i-1] == C[i+j-1]:
                    dp[i][j] |= dp[i-1][j]
                    print("Match A[%d]=%s with C[%d]=%s" % (i-1, A[i-1], i+j-1, C[i+j-1]))
                if B[j-1] == C[i+j-1]:
                    dp[i][j] |= dp[i][j-1]
                    print("Match B[%d]=%s with C[%d]=%s" % (j-1, B[j-1], i+j-1, C[i+j-1]))
        
        print("Final result:", dp[n][m])
        return dp[n][m]

算法及复杂度

  • 算法：动态规划
  • 时间复杂度：，需要填充整个 表
  • 空间复杂度：，需要二维 数组