如何检查一个列表（字符串）是否包含另一个列表（字符串），并考虑顺序？

Question

我有两个列表(或字符串): 一个较大，另一个较小。我想检查较大的一个(A)是否包含了较小的一个(B)。

我的期望如下:

情况1. B是A的子集。

A = [1,2,3]
B = [1,2] 
contains(A, B) = True

情况2：B不是A的子集，但在A中维护了顺序[1,2]

A = [1,3,2]
B = [1,2]
contains(A, B) = True

案例3. 错误，因为4不属于A

A = [1,3,2]
B = [1,4]
contains(A, B) = False

案例4. 该语句为False，因为A中未保持顺序[2,1]，尽管A包含1和2。

A = [1,3,2]
B = [2,1]
contains(A, B) = False

A和B可以是字符串。

- Gilseung Ahn

---

这些列表中是否有重复项？ - zmike

Answer 1

直接命令式方法

我相信检查一个列表是否是另一个列表的子列表是一种经典的贪心算法。我们可以扫描较大的列表，按顺序尝试在较小的列表中找到每个项。我们永远不需要回溯，因为每个元素的第一次出现都是可以接受的。

def contains(larger, smaller):
  # Take an iterator so that we always pick up where we left off.
  larger_iter = iter(larger)
  for s in smaller:
    for l in larger_iter:
      if s == l:
        break
    else:
      # We'll enter the else block if we *didn't* break in the loop,
      # in which case we never found a match for s.
      return False
  return True

这将在较大列表的尺寸上线性运行，因为我们最多只迭代一次。

函数式方法

编辑。 昨晚我在想是否有一个更小（行数）但仍然是线性的解决方案，现在我找到了一个我喜欢的。

def contains(larger, smaller):
  larger_iter = iter(larger)
  return all(s in larger_iter for s in smaller)

这里遵循与上文完全相同的算法，只是使用高级函数来处理一些簿记事项。 larger_iter中的s 对应于具有else块的内部for循环，而带有生成器的all对应于外部for循环。

- Chris Bouchard

---

这个答案是正确和高效的，这比所有其他现有的答案（包括被接受的答案）都要好。 - Cireo

Answer 2

我相信如果你不从子列表中删除不在测试列表中的元素，那么这个答案应该可以工作。因此，对于提供的第一种方法而言，应该是这样的

def contains(testList, subList):
   shared = [x for x in testList if x in subList]
   return shared == subList

你还可以将子列表转换为适用于非列表输入的格式。

def contains(testList, subList):
   shared = [x for x in testList if x in subList]
   return shared == list(subList)

- duckboycool

---

如果testList中有重复项，这段代码还能正常工作吗？我认为那样的话，shared中也会有重复项，两个列表就不一定相等了。 - Chris Bouchard

这是O(NM)而不是O(N+M)，并且对于重复项会失败，例如"batman"包含"bam"，但此函数将返回False。 - Cireo

Answer 3

你可以将列表转换为set()组。例如：

A = set(A)
B = set(B)
print(A <= B)

你可以使用a <= b方法进行子集操作。祝工作愉快。

- eminaruk

---

我猜在这种情况下，@GilseungAhn想要的是B <= A。 - zmike

这不会忽略顺序吗？就像 OP 的最后一个例子 [2, 1]？ - Chris Bouchard

Answer 4

你可以使用 collections.deque 来实现一个 O(n) 的解决方案：

from collections import deque
def contains(a, b):
  b = deque(b)
  for i in a:
     if b and i == b[0]:
        _ = b.popleft()
  return not bool(b)

data = [([1, 2, 3], [1, 2]), ([1, 3, 2], [1, 2]), ([1, 3, 2], [1, 4]), ([1, 3, 2], [2, 1])]
print([contains(*i) for i in data])

输出

[True, True, False, False]

- Ajax1234