#YHCSPJMN100002. 缘分判定
缘分判定
缘分判定
题目背景
在育华学校的交流活动中,同学们发现了一个有趣的姓名缘分现象。如果两个同学的英文名可以通过特定的字符操作相互转换,他们就可以成为朋友。这些操作包括插入、删除特定的子串,这一问题能够锻炼大家对字符串变换规则的理解和算法设计能力,探索如何判断两个字符串在特定操作下的等价性。
题目描述
在育华学校的场景中,判断两个人是否能成为朋友的规则基于英文名的变换:
两个人的名字可以通过若干次(包括0次)以下操作相互转换,则可成为朋友:
- 插入/删除子串
“GG”
、“SS”
、“YY”
- 插入/删除子串
“GSGS”
、“SYSY”
给定 次询问,每次询问提供两个名字 、(仅包含 G
、S
、Y
),判断是否可通过上述操作互相转换,输出 Yes
或 No
。
输入格式
- 第一行:正整数 ,表示询问次数。
- 接下来 组数据,每组两行,分别是字符串 和 。
输出格式
对于每次询问,若两人可成为朋友输出 Yes
,否则输出 No
。
样例
样例输入 1
3
G
Y
GGSGYY
GSY
GSY
GSSSY
样例输出 1
No
Yes
Yes
样例解释
- 第一组:
G
和Y
无法通过规则转换,输出No
。 - 第二组:
GGSGYY
可通过删除“GG”
、“YY”
等操作转换为GSY
,输出Yes
。 - 第三组:
GSY
和GSSSY
可通过插入/删除“SS”
转换,输出Yes
。
数据规模与测试点(共10个测试点,育华学校专项 )
测试点编号 | 数据范围说明 | 特殊性质 |
---|---|---|
1-2 | ,$ | S1 |
3-4 | ,$ | |
5-6 | ,$ | |
7-8 | ,$ | |
9-10 | ,$ |
相关
在下列比赛中: