2020年网易算法笔试题第四题python实现

优秀的01序列

1 如果序列S,T是优秀的，则序列S+T是优秀的，+被定义为按数学连接两个序列，即”010”+”110”=”010110”

2 如果序列S是优秀的，则序列rev(S)也是优秀的。rev(S) 被定义为按位翻转（0变1,1变0）序列S，并删去前导零。例如rev(” 1100101”)=“11010”

现在请你判断序列T是不是优秀的

输入描述

第一行数据组数T，表示有T组数据

每组数据的第一行是一个01序列，表示序列S。第二行是另一个01序列，表示序列T

1<=|S|,|T|<=1000,S,T不含前导零。

输出描述

对于每组数据，一行输出 YES或 NO，表示序列T是不是优秀的（大小写敏感）

示例

输入

1100

110011

输出

YES

示例2

输入

1000

100001111

输出

n = int(input())
for i in range(n):
    S = input()
    T = input()
    ST = S + T
    S_list = list(S)
    ST_list = list(ST)
    all_S = []
    while S_list:
        all_S.append(''.join(S_list))
        for j, value in enumerate(S_list):
            if value == '1':
                S_list[j] = '0'
            else:
                S_list[j] = '1'
        while S_list and S_list[0] == '0':
            S_list.pop(0)
    while ST_list:
        for j, value in enumerate(ST_list):
            if value == '1':
                ST_list[j] = '0'
            else:
                ST_list[j] = '1'
        while ST_list and ST_list[0] == '0':
            ST_list.pop(0)
        if ''.join(ST_list) in all_S:
            print('YES')
            break
    else:
        print('NO')

以上为个人思考结果，未经严格验证，如有错误还望见谅和指正。

利用正则表达式进行判断，T是否属于S利用规则二所形成的序列集合所构成的（规则一）

但是python中是不包含判断字符串是否符合某个正则表达式的方法用search代替，通过设定限制进行，因此可能会有问题

import re
n = int(input())
for i in range(n):
    S = input()
    T = input()
    S_list = list(S)
    T_list = list(T)
    all_S = []
    while S_list:
        all_S.append(''.join(S_list))
        for j, value in enumerate(S_list):
            if value == '1':
                S_list[j] = '0'
            else:
                S_list[j] = '1'
        while S_list and S_list[0] == '0':
            S_list.pop(0)
    print(all_S)
    gz = '(' + '|'.join(all_S) + ')' + '+'
    pattern = re.compile(gz)
    res = pattern.search(T)
    print(res[0])
    if res and res[0] == T:
        print('YES')
    else:
        print('NO')

#网易##笔试题目##题解#