zipper-题解 DFS搜索算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了zipper-题解 DFS搜索算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1343字，纯文字阅读大概需要2分钟。

内容图文

zipper-题解(DFS搜索算法)

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

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

输出格式
每行如果信息为真，则打印 Data set n：yes
每行如果信息为假，则打印 Data set n：no
n代表序号。

样例输入
3
cat tree tcraete
cat tree catrtee
cat tree cttaree
样例输出
Data set 1:yes
Data set 2:yes
Data set 3:no

#include <bits/stdc++.h>
using namespace std;
string a, b, c;
bool flag;
int la, lb, lc, n, kase = 0;
void dfs(int x, int y, int z) {
	if(x == la && y == lb && z == lc) flag = true;
	if(flag) return;
	if(a[x] == c[z]) dfs(x + 1, y, z + 1);
	if(b[y] == c[z]) dfs(x, y + 1, z + 1);
}
int main() {
	cin >> n;
	while(n--) {
		flag = false;
		cin >> a >> b >> c;
		la = a.length(), lb = b.length(), lc = c.length();
		dfs(0, 0, 0);
		cout << "Data set " << ++kase << ":" << (flag ? "yes\n" : "no\n");
	}
	return 0;
}

内容总结

以上是互联网集市为您收集整理的zipper-题解 DFS搜索算法全部内容，希望文章能够帮你解决zipper-题解 DFS搜索算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---