XMOJ 6. 交叉队列
题目：6. 交叉队列
描述:
给出三个队列 s1，s2，s3 ，判断 s3 是否是由 s1 和 s2 交叉得来。 如：s1 为 aabcc ， s2 为 dbbca。 当 s3 为 aadbbcbcac 时，返回 true（即将 s1 拆成三部分： aa，bc，c 分别插入 s2 对应位置） 否则返回 false。
输入:
aabcc,dbbca,aadbbcbcac
输出:
true
输入样例:
aabcc,dbbca,aadbbcbcac
aabcc,dbbca,aadbbbaccc
a,b,ab
a,b,ba
a,b,ac
abc,bca,bcaabc
abc,bca,aabbcc
输出样例:
true
false
true
true
false
true
false
方法：动态规划
思路：动态规划。当arr3[i + j - 1] == arr1[i - 1]时，dp[i][j] = dp[i][j] | dp[i - 1][j]。当arr3[i + j - 1] == arr1[j - 1]时，dp[i][j] = dp[i][j] | dp[i][j - 1]。arr1、arr2、arr3代表s1、s2、s3，dp[i][j]表示arr1的前i个字符和arr2的前j个字符是否能够组成arr3前i + j个字符，等于1表示能组成，等于0表示不能组成。
运行数据：最大执行时间：85.43 ms，最大内存开销：17352 KiB
复杂度分析：
由于输入数据组数无法确定，时间复杂度和空间复杂度只考虑一组数据。
- 时间复杂度：O(n * m)，n为s1的长度，m为s2的长度。
- 空间复杂度：O(n * m)，n为s1的长度，m为s2的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| import java.util.Scanner;
public class Main {
public static void main(String args[]) {
Scanner scan = new Scanner(System.in);
String line;
while (scan.hasNextLine()) {
line = scan.nextLine().trim();
String[] strs = line.split(",");
System.out.println(judge(strs));
}
}
private static boolean judge(String[] strs) {
char[] arr1 = strs[0].toCharArray();
char[] arr2 = strs[1].toCharArray();
char[] arr3 = strs[2].toCharArray();
int len1 = arr1.length;
int len2 = arr2.length;
int len3 = arr3.length;
if (len3 != len1 + len2) {
return false;
}
if (len1 == 0) {
return strs[1].equals(strs[2]);
}
if (len2 == 0) {
return strs[0].equals(strs[2]);
}
int[][] dp = new int[len1 + 1][len2 + 1];
dp[0][0] = 1;
for (int i = 1; i <= len1; i++) {
if (arr1[i - 1] == arr3[i - 1]) {
dp[i][0] = dp[i - 1][0];
}
}
for (int i = 1; i <= len2; i++) {
if (arr2[i - 1] == arr3[i - 1]) {
dp[0][i] = dp[0][i - 1];
}
}
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (arr3[i + j - 1] == arr1[i - 1]) {
dp[i][j] = dp[i][j] | dp[i - 1][j];
}
if (arr3[i + j - 1] == arr2[j - 1]) {
dp[i][j] = dp[i][j] | dp[i][j - 1];
}
}
}
return dp[len1][len2] == 1;
}
}
|
学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。
才疏学浅，若有错误或不当之处，可批评指正，还请见谅！
