PAT乙级1003-我要通过

题意

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。

输入样例：

1
2
3
4
5
6
7
8
9
10
11
10
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA
APT
APATTAA

点击并拖拽以移动

输出样例：

1
2
3
4
5
6
7
8
9
10
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为界分为三段来做条件判断。

代码实现

使用简单的循环和条件语句实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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点击并拖拽以移动​

正则表达式求解

1
2
3
4
5
6
7
8
9
10
11
12
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')