python - 考虑顺序如何检查列表(字符串)是否包含另一个列表(字符串)

Question

我有两个列表(或字符串):一个大，另一个小。
我想检查较大的(A)是否包含小的(B)。
我的期望如下:
案例 1. B 是 A 的子集

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

情况 2. B 不是 A 的子集，但顺序 [1,2] 保持在 A 中

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. 错误，因为顺序 [2,1] 未在 A 中维护，即使 A 包含 1 和 2。

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

A 和 B 可以是字符串。

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)

这遵循与上面完全相同的算法，只是使用更高级别的函数来处理一些簿记。 s in larger_iter对应于带有 else 块的内部 for 循环，以及 all with generator 对应于外部 for 循环。