如何从字符串中找出最小子字符串

Question

我试图从字符串中找到最小的子字符串（包含 set 的所有值）

例如：

Input = 'xTxxOxxVxxOxVxxTxxxOxVxTxxxOxxTxVx'
Set = 'OTV'
Output = OxVxT

Input = 'UresqTcdvavUssTss'
Set = 'UT'
Output = UssT

因为< code>OxVxT是示例1中最小的子串(包含集合的所有元素),所以我为它编写了代码，但这不是最好的方法，也不适用于所有示例，我没有通过我的代码找到最小的子串，我的代码如下:

def Fun(S, T):
    lst=[]
    lst1=[]
    lst2=[]
    for t in T:
        if t not in S: return False
    T = list(T)
    Z= list(T)
    C = list(T)
    for i in range(len(S)):
        if S[i] in T:
            lst.append(i)
            T.remove(S[i])
        if len(T)==0:break
    print (lst)
    U=(max(lst))
    for u in range(U+1,len(S)):
        if S[u] in Z:
            lst1.append(u)
            Z.remove(S[u])
        if len(Z)==0:break
    print (lst1)
    Q = (max(lst1))
    for u in range(Q+1,len(S)):
        if S[u] in C:
            lst2.append(u)
            C.remove(S[u])
        if len(C)==0:break
    print (lst2)
Str = 'xTxxOxxVxxOxVxxTxxxOxVxTxxxOxxTxVx'
Set = 'OTV'
Fun(Str,Set)

我找到所有可能的子字符串索引，然后找到它们之间的距离，并且距离最短的子字符串是字符串中最小的子字符串。我的代码不能处理所有测试用例，也没有给出正确的结果。

Answer 1

这运行O(S T)，需要python 3.7

def Func(S,T):
    s=set(S)
    d={}
    minLen, minBegin=len(T)+1,len(T)+1
    for i,c in enumerate(T):
        if c in s:
            if c in d:
                del d[c]
            d[c]=i
            if len(d)==len(s):
                for k,v in d.items():
                    if i-v+1<minLen:
                        minLen, minBegin=i-v+1,v
                    break
    if minBegin<len(T):
        return T[minBegin:minBegin+minLen]

print(Func('UT', 'UresqTcdvavUssTss')) #Output = UssT
print(Func('OTV', 'xTxxOxxVxxOxVxxTxxxOxVxTxxxOxxTxVx')) #Output = OxVxT
print(Func('A', 'xTxxOxxVxxOxVxxTxxxOxVxTxxxOxxTxVx')) #Output = None