“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于PAT的“答案正确”大派送 —— 只要读入的字符串满足下列条件,系统就输出“答案正确”,否则输出“答案错误”。
得到“答案正确”的条件是:
1. 字符串中必须仅有P, A, T这三种字符,不可以包含其它字符;\
任意形如 xPATx 的字符串都可以获得“答案正确”,其中 x 或者是空字符串,或者是仅由字母 A 组成的字符串;\如果 aPbTc 是正确的,那么 aPbATca 也是正确的,其中 a, b, c 均或者是空字符串,或者是仅由字母 A 组成的字符串。现在就请你为PAT写一个自动裁判程序,判定哪些字符串是可以获得“答案正确”的。
输入格式: 每个测试输入包含1个测试用例。第1行给出一个自然数n (<10),是需要检测的字符串个数。接下来每个字符串占一行,字符串长度不超过100,且不包含空格。
输出格式:每个字符串的检测结果占一行,如果该字符串可以获得“答案正确”,则输出YES,否则输出NO。
输入样例:
8 PAT PAAT AAPATAA AAPAATAAAA xPATx PT Whatever APAAATAA输出样例:
YES YES YES YES NO NO NO NO下面我们分析一下该问题(只需要代码的同学可以直接看最后代码部分):
这是一道典型的字符串匹配问题,是十分简单的,但是问题的描述让人有点搞不清楚题意,我在看满分答案之前也没有完全理解该题的意思。
第一个条件 :
1:任意形如xPATx的字符串都可以获得“答案正确”,其中x或者是空字符串,或者是仅由字符A组成的字符串
原字符串中包含'PAT'这个子字符串。且其余字符全是字符'A'
第二个条件:
2:如果aPbTc是正确的,那么aPbATca也是正确的,其中a,b,c均或者是空字符串,或者是仅由字母A组成的字符串。
我们是不是可以理解为,有形如'APATA'的字符串,它是正确的,且在中间,和末尾各加一个字符'A'也是“正确答案”,显然这样理解是正确的。那么加多个字符'A'是不是也正确呢?从实验用例来看AAPAATAAAA是正确答案,我们可能会认为是不是在PAT的任意位置加任意个数的字符'A'都是正确的呢?从最后一个实验用例来看显然是错误的。
从其他满分答案来看,有以下约束:
有形如xPyTx的字符串,x是空字符串,或者是仅由字符A组成的字符串,y是仅由字符A组成的字符串,我们以字符P,T进行分段,P前段为a,P T之间为b,T之后为c,则若它是正确答案,有c=a*len(b)
下面我们来看两个实验用例:
①字符串AAPAATAAAA
a段:AA b段:AA c段:AAAA
有 AAAA=AA*len(AA)
AAAA=AA*2
所以是正确答案
②字符串APAAATAA
a段:A b段:AAA c段:AA
有AA=A*len(AAA)
等式不成立
所以是错误答案
理解了以上条件后,就可以很好地解决这道题了,算法的基本思想就是,以P T为界分为三段来做条件判断。
一:使用简单的循环和条件语句实现
def test(a): x = -1 y = -1 for i in range(len(a)):#找出P,T的位置 if (a[i]=='P'): x = i if (a[i]=='T'): y = i if (x==-1 or y==-1):#如果找不到P,T则返回0 return 0 if (x>y):#P在T的后面,返回0 return 0 if (y==x+1):#P,T之间没有字符,返回0 return 0 if (x!=0):#字符串不以P开头 b = a[0:x] else:#字符串以P开头 b = [] c = a[x+1:y] if (y!=len(a)-1):#字符串不以T结尾 d = a[y+1:len(a)] else:#字符串以T结尾 d = [] for i in b:#判断各个分段是否是字符A组成 if (i!='A'): return 0 for i in c: if (i!='A'): return 0 for i in d: if (i!='A'): return 0 if (d==b*len(c)):#条件判断 return 1 else: return 0 n = input() for i in range(int(n)): s = input() if (test(s)==1): print('YES') else: print('NO')除了上述方法外,我们还可以使用正则表达式来对字符串进行匹配
下面我们简单介绍一下正则表达式,和使用到的几个操作符
正则表达式是对字符串的一种逻辑公式,就是实现定义好一些特定的字符,及这些特定字符的组合,组成一个“规则字符串”,这个“规则字符串”用来表达对字符串的一种过滤逻辑。通常用来检索,替换那些符合摸个模式的文本,常用于字符串操作。
.
表示任何单个字符 [ ]字符集,对单个字符给出取值范围[abc]表示a,b,c [a-z]表示a到z的所有单个字符[^]非字符集,对单个字符给出排除范围[^abc]表示非a或b或c的单个字符*前一个字符的零次或无限次扩展abc*表示ab,abc,abcc,abccc等+前一个字符的一次或无限次扩展abc+表示abc,abcc,abccc等?前一个字符零次或一次扩展abc?表示ab,abc|左右表达式任意一个abc|def表示abc,def{m}扩展前一个字符m次ab{2}c表示abbc{m,n}扩展前一个字符m至n次(含n次)ab{1,2}表示abc,abbc^匹配字符串开头^abc表示abc且在一个字符串的开头$匹配字符串结尾abc$表示abc且在一个字符串的结尾()分组标记,内部只能使用|操作符(abc)表示abc,(abc|def)表示abc,def\d数字,等价于[0-9]综上所述,问题中的字符串用正则表达式表示为:A*PA+TA*
二:正则表达式求解
import re n=input() for i in range(int(n)): s=input() if re.match(r'A*PA+TA*',s): #在字符串中进行匹配 a=re.split(r'[P|T]',s) #以字符P,T进行分段 if a[0]*len(a[1])==a[2]: #条件判断 print('YES') else: print('NO') else: print('NO')