函数 return 第一个可能的子串包含子串的所有元素

Question

如何将 myStr 函数修改为 return 包含 str2 所有元素的第一个可能的子字符串（从左遍历）。例如：给定 str1 = 'xBxxAxxCxxAxCxxBxxxAxCxBxxxAxxBxCx' 和 str2 = "ABC"，函数应该 return "BxxAxxC".

str1 = input("Enter the first string: ")
str2 = input("Enter the second string to check if the characters exist in the first string: ")

def myStr(str1, str2):
    
    if all(i in str1 for i in str2):
        return True
    else:     
        return False

myStr(str1, str2)

Answer 1

假设 str2 中不是的最左边的字符应该被排除，您可以执行以下操作：

为str2
迭代 str1 中的字符并将它们从该集合中删除。
一旦集合为空，您就知道条件已满足。
要排除最左边的字符，请跟踪第一个与集合中的字符匹配的索引。

def myStr(str1, str2):
    todo = set(str2)
    start = -1
    for i, ch in enumerate(str1):
        if not todo:
            return str1[start:i]
        if ch in todo:
            todo.discard(ch)
            if start < 0:
                start = i

Answer 2

您可以使用 set 操作，对于每个前缀检查所有字母是否在

set(str2) - set(str1[:1])

set(str2) - set('xB')       # {'C', 'A'}
set(str2) - set('xBxxA')    # {'C'}
set(str2) - set('xBxxAxxC') # set()

def myStr(str1, str2):
    chars_to_have = set(str2)
    i = 0
    while chars_to_have - set(str1[:i]) != set() and i < len(str1):
        i += 1
    return str1[:i]

Answer 3

如果str2不包含任何重复的字母，您可以将其字符映射到它们在str1中的第一个位置，并获取最小和最大位置之间的范围：

例如：

str1   = 'xBxxAxxCxxAxCxxBxxxAxCxBxxxAxxBxCx'
str2   = "ABC"

pos    = [str1.find(c) for c in str2]
result = str1[min(pos):max(pos)+1]

print(result) # BxxAxxC

如果 str2 的所有字符未出现在 str1 中，这将产生一个空字符串

如果str2可以包含重复的字母，那么位置列表（pos）需要包含重复字符的多个位置：

pos = [i for r in [list(str2)] for i,c in enumerate(str1) 
       if c in r and not r.remove(c)]

函数 return 第一个可能的子串包含子串的所有元素

function to return the first possible substring containing all the elements of substring

python

string

substring