天梯赛真题L1-6(字符串)python题解

题目

英语老师要求学生按照如下规则写一串字母：

• 如果写了某个大写字母，下一个就必须写同个字母的小写，或者写字母表中下一个字母的大写；
• 如果写了某个小写字母，下一个就必须写同个字母的大写，或者写字母表中前一个字母的小写；
• 当然也可以什么都不写，就结束这个字母串。

例如 aAaABCDdcbBC 就是一个合法的字母串；而 dEFfeFGhI 就是非法的。注意 a 没有前一个字母， Z 也没有下一个字母。

现在面对全班学生交上来的作业，老师请你写个程序自动批改。

限制

代码长度限制16 KB、时间限制800 ms、内存限制64 MB

输入格式：

输入在第一行给出一个不超过 100 的正整数 N。随后 N 行，每行给出一位学生的作业，即仅由英文字母组成的非空字母串，长度不超过 2×106。

输出格式：

对每位学生的作业，如果正确就在一行中输出 Y，否则输出 N。

输入样例：

2
aAaABCDdcbBC
dEFfeFGhI

输出样例：

Y
N

题解

N = int(input())
def isright(charlist):
    count = 0
    for i in range(len(charlist)-1):
        if charlist[i] >= 'a' and charlist[i] <= 'z':
            if charlist[i+1] == charlist[i].upper() or charlist[i+1] == chr(ord(charlist[i])-1):
                continue # 这里使用continue会提高代码运行速度
            else:
                count = 1
                break
        else:
            if charlist[i+1] == charlist[i].lower() or charlist[i+1] == chr(ord(charlist[i])+1):
                continue
            else:
                count = 1
                break
    if count == 0:
        print("Y")
    else:
        print("N")
for n in range(N):
    charlist = input()
    if len(charlist) == 0 or len(charlist) == 1:
        print("Y")
        continue
    isright(charlist)

👆是作者目前的最优解。

作者还曾尝试不用函数封装，但运行超时👇：

N = int(input())
for n in range(N):
    charlist = input()
    if len(charlist) == 0 or len(charlist) == 1:
        print("Y")
        continue
    count = 0
    for i in range(len(charlist)-1):
        if charlist[i] >= 'a' and charlist[i] <= 'z':
            if charlist[i+1] == charlist[i].upper() or charlist[i+1] == chr(ord(charlist[i])-1):
                continue
            else:
                count = 1
                break
        else:
            if charlist[i+1] == charlist[i].lower() or charlist[i+1] == chr(ord(charlist[i])+1):
                continue
            else:
                count = 1
                break
    if count == 0:
        print("Y")
    else:
        print("N")

另外还需注意的是，在for循环中使用continue对提高代码运行很有效，即使条件判断后已将没有可执行的语句了，在后面使用continue依然比pass快！

算法 — Apr 23, 2022