PAT乙级1003-我要通过

PAT乙级1003-我要通过

https://www.bilibili.com/video/BV1VS4y127Kz

题意

range（10）是指0,1,2,3,4,5,6,7,8,9

PAT (Basic Level) Practice （中文）

1003 我要通过！ (20 分)

“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“答案正确”大派送 —— 只要读入的字符串满足下列条件，系统就输出“答案正确”，否则输出“答案错误”。

得到“答案正确”的条件是：

1. 字符串中必须仅有 P、 A、 T这三种字符，不可以包含其它字符；
2. 任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串；
3. 如果 aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a、 b、 c 均或者是空字符串，或者是仅由字母 A 组成的字符串。

现在就请你为 PAT 写一个自动裁判程序，判定哪些字符串是可以获得“答案正确”的。

输入格式：

每个测试输入包含 1 个测试用例。第 1 行给出一个正整数 n (≤10)，是需要检测的字符串个数。接下来每个字符串占一行，字符串长度不超过 100，且不包含空格。

输出格式：

每个字符串的检测结果占一行，如果该字符串可以获得“答案正确”，则输出 YES，否则输出 NO。

输入样例：

10
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA
APT
APATTAA

输出样例：

YES
YES
YES
YES
NO
NO
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')

除了上述方法外，我们还可以使用正则表达式来对字符串进行匹配

下面我们简单介绍一下正则表达式，和使用到的几个操作符

正则表达式是对字符串的一种逻辑公式，就是实现定义好一些特定的字符，及这些特定字符的组合，组成一个“规则字符串”，这个“规则字符串”用来表达对字符串的一种过滤逻辑。通常用来检索，替换那些符合摸个模式的文本，常用于字符串操作。

img

​

正则表达式求解

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')