字符混编

[编程题]字符混编

热度指数：3532 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

A、B和C。如果C包含且仅包含来自A和B的所有字符，而且在C中属于A的字符之间保持原来在A中的顺序，属于B的字符之间保持原来在B中的顺序，那么称C是A和B的混编。实现一个函数，判断C是否是A和B的混编。

给定三个字符串A,B和C，及他们的长度。请返回一个bool值，代表C是否是A和B的混编。保证三个串的长度均小于等于100。

测试样例：

"ABC",3,"12C",3,"A12BCC",6

返回：true

算法知识视频讲解

推荐

orgcheng

假设A = "ABC", B = "AABC", C="AAABCBC"

// 定义辅助数组
boolean[][] dp = boolean new [101][101];

未了方便处理，在A和B的前面添加一个空字符。dp的初始化如下图

下面就开始找dp的状态转移方程了
dp[i][j]就表示 A[0 ~ i-1]和B[0 ~ j-1]是否构成C[ 0 ~ i+j-1]

dp[i][j]=true的第一种情况是

dp[i][j-1] == true && B[j-1] == C[i+j-1]

dp[i][j]=true的第二种情况是

dp[i-1][j] == true && A[i-1] == C[i+j-1]

dp绘制完成后，如下图所示

只要dp[n][m] = true,结果就是true
其中n为A字符串的长度，m为B字符串的长度。

整体代码如下

import java.util.*;

public class Mixture {
	public boolean chkMixture(String A, int n, String B, int m, String C, int v) {
		// 边界情况处理
		if (m + n != v)
			return false;
		
		// 默认初始化为false
		boolean[][] dp = new boolean[101][101];

		dp[0][0] = true;
		// 初始化第0行
		for (int i = 1; i <= m; ++i) {
			if (B.charAt(i - 1) == C.charAt(i - 1))
				dp[0][i] = true;
			else
				break;
		}
		// 初始化第0列
		for (int i = 1; i <= n; ++i) {
			if (A.charAt(i - 1) == C.charAt(i - 1))
				dp[i][0] = true;
			else
				break;
		}

		
		/*
		 * 状态转移方程
		 *  dp[i][j] = 
		 * 
		 *  case 1: dp[i][j-1] == true && B[j-1] == C[i+j-1]
		 *  
		 *  case 2: dp[i-1][j] == true && A[i-1] == C[i+j-1]
		 * 
		 */
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= m; ++j) {
				if (!dp[i][j]) {
					// dp[i-1][j] = true && A[i-1] == C[i+j-1]
					if (dp[i - 1][j] && A.charAt(i - 1) == C.charAt(i + j - 1))
						dp[i][j] = true;

					// dp[i][j-1] == true && B[j-1] == C[i+j-1]
					if (dp[i][j - 1] && B.charAt(j - 1) == C.charAt(i + j - 1))
						dp[i][j] = true;
				}
			}
		}
		return dp[n][m];
	}
}

上的代码使用了额外的空间，时间复杂度为O(n^2)
虽然没有递归调用代码简洁，但是如果每个字符串的长度过长时，递归容易出现栈溢出。

编辑于 2015-08-11 15:12:54 回复(4)

Java

福尔摩斯易

我是个铁憨憨，竟然用了个三位数组来做。

import java.util.*;

public class Mixture {
    public boolean chkMixture(String A, int n, String B, int m, String C, int v) {
        // write code here
        if (n + m > v) {
            return false;
        }
       
        boolean[][][] dp = new boolean[n + 1][m + 1][v + 1];
        for (int i = 0; i <= v; ++i) {
            dp[0][0][i] = true;
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = i; j <= v; ++j) {
                dp[0][i][j] = dp[0][i][j - 1] || (dp[0][i - 1][j - 1] && B.charAt(i - 1) == C.charAt(j - 1));
            }
        }

        for (int i = 1; i <= n; ++i) {
            for (int j = i; j <= v; ++j) {
                dp[i][0][j] = dp[i][0][j - 1] || (dp[i - 1][0][j - 1] && A.charAt(i - 1) == C.charAt(j - 1));
            }
        }

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                for (int k = 1; k <= v; ++k) {
                    dp[i][j][k] = dp[i][j][k - 1] || (dp[i - 1][j][k - 1] && A.charAt(i - 1) == C.charAt(k - 1)) || (dp[i][j - 1][k - 1] && B.charAt(j - 1) == C.charAt(k - 1));
                }
            }
        }

        return dp[n][m][v];
    
    }
}

发表于 2020-03-02 20:43:10 回复(0)

Java

詆調壹點

import java.util.*;
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];
		for (int i = 1; i<= n; i ++ ) if(A.charAt(i - 1) == C.charAt(i - 1)) dp[i][0] = true;
		for (int i = 1; i<= m; i ++ ) if(B.charAt(i - 1) == C.charAt(i - 1)) dp[0][i] = true;
		for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) if(C.charAt(i + j - 1) == A.charAt(i - 1) || C.charAt(i + j - 1) == B.charAt(j - 1)) dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
		return dp[n][m];
	}
}

编辑于 2016-10-18 11:24:37 回复(0)

Java

JustYoung

import java.util.*;

public class Mixture {
    public boolean chkMixture(String A, int n, String B, int m, String C, int v) {
        // write code here
        char[] a = A.toCharArray();
        char[] b = B.toCharArray();
        char[] c = C.toCharArray();
        boolean[][] dp = new boolean[a.length + 1][b.length + 1];
        dp[0][0] = true;
        for (int i = 1; i <= a.length; ++i) {
            if (a[i - 1] == c[i - 1]) {
                dp[i][0] = true;
            } else {
                break;
            }
        }
        for (int j = 1; j <= b.length; ++j) {
            if (b[j - 1] == c[j - 1]) {
                dp[0][j] = true;
            } else {
                break;
            }
        }

        for (int i = 1; i <= a.length; ++i) {
            for (int j = 1; j <= b.length; ++j) {
                if (dp[i - 1][j] && c[i + j - 1] == a[i - 1]) {
                    dp[i][j] = true;
                    continue;
                }
                if (dp[i][j - 1] && c[i + j - 1] == b[j - 1]) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[a.length][b.length];
    }
}

发表于 2016-09-10 13:57:10 回复(0)