#YHCSPJMN100002. 缘分判定

缘分判定

缘分判定

题目背景

在育华学校的交流活动中,同学们发现了一个有趣的姓名缘分现象。如果两个同学的英文名可以通过特定的字符操作相互转换,他们就可以成为朋友。这些操作包括插入、删除特定的子串,这一问题能够锻炼大家对字符串变换规则的理解和算法设计能力,探索如何判断两个字符串在特定操作下的等价性。

题目描述

在育华学校的场景中,判断两个人是否能成为朋友的规则基于英文名的变换:
两个人的名字可以通过若干次(包括0次)以下操作相互转换,则可成为朋友:

  1. 插入/删除子串 “GG”“SS”“YY”
  2. 插入/删除子串 “GSGS”“SYSY”

给定 T T 次询问,每次询问提供两个名字 S1 S1 S2 S2 (仅包含 GSY ),判断是否可通过上述操作互相转换,输出 YesNo

输入格式

  1. 第一行:正整数 T T ,表示询问次数。
  2. 接下来 T T 组数据,每组两行,分别是字符串 S1 S1 S2 S2

输出格式

对于每次询问,若两人可成为朋友输出 Yes,否则输出 No

样例

样例输入 1

3  
G  
Y  
GGSGYY  
GSY  
GSY  
GSSSY  

样例输出 1

No  
Yes  
Yes  

样例解释

  • 第一组:GY 无法通过规则转换,输出 No
  • 第二组:GGSGYY 可通过删除 “GG”“YY” 等操作转换为 GSY,输出 Yes
  • 第三组:GSYGSSSY 可通过插入/删除 “SS” 转换,输出 Yes

数据规模与测试点(共10个测试点,育华学校专项 )

测试点编号 数据范围说明 特殊性质
1-2 T=1 T=1 ,$ S1
3-4 T10 T \leq 10 ,$
5-6 T50 T \leq 50 ,$
7-8 T80 T \leq 80 ,$
9-10 T100 T \leq 100 ,$