字符串交错组成

[编程题]字符串交错组成

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

对于三个字符串A，B，C。我们称C由A和B交错组成当且仅当C包含且仅包含A，B中所有字符，且对应的顺序不改变。请编写一个高效算法，判断C串是否由A和B交错组成。

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

测试样例：

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

返回：true

算法知识视频讲解

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

int count=0;

int a=0;

int b=0;

for (int i=0;i<C.length();i++){

if(a<n&&C.charAt(i)==A.charAt(a)){

a++;

count++;

}

if(b<m&&C.charAt(i)==B.charAt(b)){

b++;

count++;

}

return count==v;

}

发表于 2017-07-14 16:50:11 回复(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];
		dp[0][0] = true;
		for (int i = 1; i <= n; i ++) {
			if(A.charAt(i - 1) == C.charAt(i - 1)) dp[i][0] = true;
			else break;
		}
		for (int j = 1; j <= m; j ++) {
			if(B.charAt(j - 1) == C.charAt(j - 1)) dp[0][j] = true;
			else break;
		}
		for (int i = 1; i <= n; i ++) {
			for (int j = 1; j <= m; j ++) {
				dp[i][j] = (A.charAt(i - 1) == C.charAt(i + j - 1) && dp[i - 1][j]) || (B.charAt(j - 1) == C.charAt(i + j - 1) && dp[i][j - 1]);
			}
		}
		return dp[n][m];
	}
}

编辑于 2017-03-16 22:24:40 回复(2)

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 14:00:42 回复(0)

Java