Solution - zipper

link

题目描述

天顶星人使用量子纠缠技术传送信息，量子纠缠超越了我们生活的四维时空，不受四维时空的约束，其传输信息的速度至少比光速快 \(10000\) 倍。换句话说，即使传送双方远在宇宙的两端，信息也可以瞬间到达。但天顶星人传送的信息有真有假，判断真假的方式是对三个字符串进行验证，即给三个字符串，判断第三个字符串是否由前两个字符串的一部分序列顺序组成，例如字符串 \(A\) 为 \(“cat”\)，字符串 \(B\) 为 \(“tree”\) ，字符串 \(C\) 为 \(“tcraete”\) ，字符串 \(C\) 由字符串 \(A\) 和 \(B\) 组成，则信息为真。

再比如字符串 \(A\) 为 \(“cat”\) ，字符串 \(B\) 为 \(“tree”\) ，字符串 \(C\) 为 \(“carttee”\) ，由于组成的序列顺序不对，所以信息应该是假。

输入格式

第一行有一个整数 \(N\) ，大小在 \(1 - 1000\)，代表后续有 \(N\) 行，每行有三组字符串数据，每组字符串由空格分隔开，第三组字符串数据的长度总是前两组字符串数据的长度总和。前两行字符串的长度在 \(1 - 200\) 。

输出格式

每行如果信息为真，则打印 Data set n：yes
每行如果信息为假，则打印 Data set n：no
\(n\) 代表序号。

样例

样例输入

cat tree tcraete
cat tree catrtee
cat tree cttaree

样例输出

Data set 1:yes
Data set 2:yes
Data set 3:no

思路

不难发现这时一道 贪心 搜索。
我们可以分别从每一个字符串的 \(0\) 号位开始搜索。
\(1.\) 如果当前遍历到的字符串 \(1\) 的 \(n1\) 号位与字符串 \(3\) 当前遍历到的 \(n3\) 相等的话，那么就判断 \(dfs(n1 + 1, n2, n3 + 1)\) 是否为真，如果位真。返回真，否则为假。
\(2.\) 如果当前遍历到的字符串 \(2\) 的 \(n2\) 号位与字符串 \(3\) 当前遍历到的 \(n3\) 相等的话，那么就判断 \(dfs(n1, n2 + 1, n3 + 1)\) 是否为真，如果位真。返回真，否则为假。
\(3.\) 如果当前遍历到的字符串 \(1\) 的 \(n1\) 号位与字符串 \(3\) 当前遍历到的 \(n3\) 相等且当前遍历到的字符串 \(2\) 的 \(n2\) 号位与字符串 \(3\) 当前遍历到的 \(n3\) 也相等。就分别搜索。
\(dfs(n1 + 1, n2, n3 + 1)\)
\(dfs(n1, n2 + 1, n3 + 1)\)

\(code\)

#include 
#include 
char st1[1005], st2[1005], st3[1005];//三个字符串 
int len1, len2, len3;//字符串长度 
bool dfs(int n1, int n2, int n3) {//n1表示st1用去的长度，n2表示st2用去的长度，n3表示st3用去的长度
	if (n1 == len1 && n2 == len2 && n3 == len3) return true; //如果长度用完，返回true 
	if (st3[n3] == st1[n1] && st3[n3] == st2[n2]) {//字符串1和字符串3相等或字符串2和字符串3相等 
		if (dfs(n1 + 1, n2, n3 + 1) || dfs(n1, n2 + 1, n3 + 1)) return true;//只要有一个为真，返回真 
		else return false;//否则为假 
	} else if (st3[n3] == st1[n1]) {//字符串1和字符串3相等 
		if (dfs(n1 + 1, n2, n3 + 1)) return true;//为真，返回true 
		else return false;//否则为false 
	} else if (st3[n3] == st2[n2]) {//字符串2和字符串3相等 
		if (dfs(n1, n2 + 1, n3 + 1)) return true;//为真，返回true 
		else return false;//否则为false 
	}
	return false;//没有满足条件的为假 
} 
int main() {
	int t, i = 1;
	scanf("%d\n", &t);//输入 
	while (i <= t) {
		memset(st1, 0, sizeof(st1));//清空 
		memset(st2, 0, sizeof(st2));//清空 
		memset(st3, 0, sizeof(st3));//清空 
		scanf("%s %s %s", st1, st2, st3);//输入 
		len1 = strlen(st1), len2 = strlen(st2), len3 = strlen(st3);//求长度 
		if (dfs(0, 0, 0)) printf("Data set %d:yes\n", i);//输出 
		else printf("Data set %d:no\n", i);//输出 
		i++; 
	}
	return 0;
}