PTA 7-5 子串与子列 (25 分)

原创

freesan44

修改于 2021-09-10 17:50:28

4480

文章被收录于专栏：freesan44freesan44

题目

子串是一个字符串中连续的一部分，而子列是字符串中保持字符顺序的一个子集，可以连续也可以不连续。例如给定字符串 atpaaabpabtt，pabt是一个子串，而 pat 就是一个子列。

现给定一个字符串 S 和一个子列 P，本题就请你找到 S 中包含 P 的最短子串。若解不唯一，则输出起点最靠左边的解。

输入格式：

输入在第一行中给出字符串 S，第二行给出 P。S 非空，由不超过 10

个小写英文字母组成；P 保证是 S 的一个非空子列。

输出格式：

在一行中输出 S 中包含 P 的最短子串。若解不唯一，则输出起点最靠左边的解。

输入样例：
atpaaabpabttpcat
pat
结尾无空行
输出样例：
pabt
结尾无空行

解题思路

P = str(input())
S = str(input())
# P = str("atpaaabpabttpcat")
# S = str("pat")



def isCunzai(input:str, S:str) -> bool:
    j = 0
    for i in input:
        if i == S[j]:
            j += 1
            if len(S) == j:
                return True
    return False

resList = []
PList = list(P)
left0 = S[0]
right0 = S[-1]
left0List = []
right0List = []
for index,val in enumerate(PList):
    if val == left0:
        left0List.append(index)
    if val == right0:
        right0List.append(index)
minLeng = len(P)
for i in left0List:
    for j in right0List:
        # print(i,j,P[i:j+1])
        length = j +1  - i
        if i<=j and length <= minLeng:
            PtempStr = (P[i:j+1])
            if isCunzai(PtempStr,S) == True:
                resList.append(PtempStr)
                minLeng = len(PtempStr)
                break
# print(resList)
print(min(resList,key= lambda x:len(x)))

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

数据结构