【华为OD机试2023】字符串解密（Python）

题目描述：

给定两个字符串string1和string2。

string1是一个被加扰的字符串。string1由小写英文字母（'a'~'z'）和数字字符（'0'~'9'）组成，而加扰字符串由'0'~'9'、'a'~'f'组成。string1里面可能包含0个或多个加扰子串，剩下可能有0个或多个有效子串，这些有效子串被加扰子串隔开。

string2是一个参考字符串，仅由小写英文字母（'a'~'z'）组成。

你需要在string1字符串里找到一个有效子串，这个有效子串要同时满足下面两个条件：

（1）这个有效子串里不同字母的数量不超过且最接近于string2里不同字母的数量，即小于或等于string2里不同字母的数量的同时且最大。

（2）这个有效子串是满足条件（1）里的所有子串（如果有多个的话）里字典序最大的一个。

如果没有找到合适条件的子串的话，请输出"Not Found"

示例：

输入字符串string1为"thisisanewday111forme"，输入字符串string2为"good"。string1里有效子串和加扰子串分割后可表示为："thisis"+"a"+"n"+"e"+"w"+"da"+"y"+"111f"+"orm"+"e"，去除加扰子串（"a"、"e"、"da"、"111f"、"e"）后的有效子串候选为("thisis", "n", "w", "y", "orm")。输入字符串string2里不同字母的数量为3（'g'、'o'、'd'），从有效子串候选里可以找出"orm"满足要求，其不同字母的数量为3，最接近于string2不同字母的数量。

输入描述：

input_string1

input_string2

说明：输入为两个字符串，第1行是题目里的string1（被加扰的字符串），第2行是题目里的string2（参考字符串）

输出描述：

output_string

说明：输出为一个字符串（有效字符串）

补充说明：

输入字符串string1的长度在1~100000之间，string2的长度在1~500之间

示例1

输入：

123admyffc79pt

ssyy

输出：

pt

说明：

    将输入字符串1里的加扰子串"123ad"、"ffc79"去除后得到有效子串序列："my"、"pt"，其中"my"里不同字母的数量为2（有'm'和'y'两个不同字母），"pt"里不同字母的数量为2（有'p'和't'两个不同字母）；输入字符串2里不同字母的数量为2（有's'和'y'两个不同字母）。

    可得到最终输出结果为"pt"，其不同字母的数量最接近于"ssyy"里不同字母的数量的同时字典序最大。

示例2

输入：

123admyffc79ptaagghi2222smeersst88mnrt

ssyyfgh

输出：

mnrt

说明：

    将输入字符串1里的加扰子串"123ad"、"ffc79"、"aa"、"2222"、"ee"、"88"去除后得到有效子串序列："my"、"pt"、"gghi"、"sm"、"rsst"、"mnrt"；输入字符串2里不同字母的数量为5（有's'、'y'、'f'、'g'、'h' 5个不同字母）。

    可得到最终输出结果为"mnrt"，其不同字母的数量（为4）最接近于"ssyyfgh"里不同字母的数量，其他有效子串不同字母的数量都小于"mnrt"。

示例3

输入：

abcmnq

rt

输出：

Not Found

说明：

将输入字符串1里的加扰子串"abc"去除后得到有效子串序列："mnq"；输入字符串2里不同字母的数量为2（有'r'、't'两个不同的字母）。

可得到最终的输出结果为"Not Found"，没有符合要求的有效子串，因有效子串的里不同字母的数量（为3），大于输入字符串2里的不同字母的数量

解题思路：

题目很好理解，写起来也不难，不过最好自定义函数，不然写起来太复杂了。而模块化之后就很顺畅了。

第一步：处理string1，筛选出有效子串的候选

第二步：处理第一步中得到的列表，用set()的长度来统计字符串中不同字符的数量，能够省下很多操作

第三步：用sorted()处理第二步得到的列表，如果是默认的升序排列，输出列表最后一个元素即可，如果是逆序，输出第一个元素

#思路相同的优化版
string1=input()
string2=input()

def youxiao(s):
    if 'g'<=s<='z':
        return True
    else:
        return False
yxzc=[]
temp=[]
pre_word='a'
for word in string1:
    if youxiao(word):
        temp.append(word)
        pre_word=word
    elif not youxiao(word) and youxiao(pre_word):
        yxzc.append(''.join(temp))
        temp.clear()
        pre_word=word
if temp!=[]:
    yxzc.append(''.join(temp))

yxzc2=[]
l=len(set(string2))
max_length=0
for word2 in yxzc:
    if max_length<len(set(word2))<=l:
        yxzc2.clear()
        yxzc2.append(word2)
        max_length=len(set(word2))
    elif max_length==len(set(word2)):
        yxzc2.append(word2)
yxzc2=sorted(yxzc2,reverse=True)
print(yxzc2[0] if yxzc2!=[] else 'Not Found')




#旧版
def youxiao(st:str):
    pre_word='a'
    #存储有效子串候选的各字符
    x=[]
    #存储有效子串候选
    y=[]
    for i,word in enumerate(st):
        if '0'<=pre_word<='9' or 'a'<=pre_word<='f':
            if not('0'<=word<='9' or 'a'<=word<='f'):
                x.append(word)
        else:
            if '0'<=word<='9' or 'a'<=word<='f':
                y.append(''.join(x))
                x.clear()
            else:
                x.append(word)
        pre_word = word
        if i==len(st)-1:
            y.append(''.join(x))
    return y

def max_ziji(lst:list,st:str):
#存储符合要求的字符串
    ls1=[]
    count=0
#set()去重后，len()就是不同字符的数量
    target=len(set(lst))
    for word in lst:
        temp=len(set(word))
        if temp<=target:
            if temp>count:
                ls1.clear()
                ls1.append(word)
                count=temp
            elif temp==count:
                ls1.append(word)
    return ls1


string1=input()
string2=input()
list_youxiao=youxiao(string1)
#两个if，判断如果输出的是空列表[]就返回Not Found
if not list_youxiao:
    print('Not Found')
else:
    list_max_ziji=max_ziji(list_youxiao,string2)
    if not list_max_ziji:
        print('Not Found')
    else:
#sort()升序排列，所以是取最后一个
        target_str=sorted(list_max_ziji)[-1]
        print(target_str)