检查列表中的所有单词是否显示为另一个lis中单词中至少一个单词的开头

Question

这是可行的，但似乎过于复杂：

s1 = list(set(['red', 'gold', 'black', 'gold']))

s2 = ['golden', 'blackstone', 'golden', 'goldlike', 'blackstone', 'golden', 'redline', 'red']

lst = []
for i in s1:
    for j in s2:
        if j.startswith(i):
            lst.append(i)
lst2 = set(lst)
if len(s1) == len(lst2):
    print(s2)

# output: ['golden', 'blackstone', 'golden', 'goldlike', 'blackstone', 'golden', 'redline', 'red']

有没有更有效、更紧凑的方法？你知道吗

Answer 1

问题是：检查列表中的所有单词是否显示为另一个列表中的单词中至少一个单词的开头。你知道吗

假设op希望S1中的所有单词至少作为S2中单词的开头出现一次。你知道吗

您可以对两个输入进行排序

def contain(s1, s2):
    count = 0
    for i in s1:
        while ( count < len(s2) and s2[count].startswith(i) == False ):
            count += 1
        if (count >= len(s2)): return False
    return True
s1 = sorted(set(['red', 'gold', 'black', 'gold', 'red', 're']))
s2 = sorted(['golden', 'blackstone', 'golden', 'goldlike', 'blackstone', 'golden', 'redline', 'red'])
print( contain(s1, s2) )

输出：

True

编辑以包含复杂性：

假设S1有n个元素，S2有m个元素。你知道吗

如果一个简单的解决方案有嵌套的循环来遍历这两个列表，那么它的复杂性将是O(n*m)。你知道吗

通过对S1和S2进行排序，我们可以降低求解的复杂性。你知道吗

排序S1：O(n*log n)，排序S2：O(m*log m)，包含：O(m)（m if m > n else n）

正如Stefan在评论中指出的，通过排序，它将比单纯的方法具有更好的复杂性。你知道吗

Answer 2

您可以使用all和any：

s1 = set(['red', 'gold', 'black', 'gold'])
s2 = ['golden', 'blackstone', 'golden', 'goldlike', 'blackstone', 'golden', 'redline', 'red']
print(all(any(i.startswith(b) for b in s1) for i in s2))

输出：

True

编辑：

检查s1中的每个元素是否出现在s2：

print(all(any(b.startswith(i) for b in s2) for i in s1))