The title

A substring is a contiguous part of a string, and a subcolumn is a subset of the string that maintains character order, either contiguous or discontiguous. For example, given the string atpaaabpabtt, pabt is a substring and PAT is a subcolumn.

Given a string S and a subcolumn P, find the shortest substring of S containing P. If the solution is not unique, the solution most to the left of the starting point is output.

Input format: The input gives the string S in the first line and P in the second line. S is non-empty and consists of no more than 10 or 14 lowercase letters. P is guaranteed to be a non-empty subcolumn of S.

Output format: Outputs the shortest substring containing P in S in one line. If the solution is not unique, the solution most to the left of the starting point is output.

Example: ATPAaabpabttPCAT PAT No blank line at the end. Example: No blank line at the end of the PABTCopy the code

Their thinking

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)))
Copy the code