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

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

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

A 和 B 可以是字符串。

Answer 1

我相信如果您只是不从子列表中删除不在测试列表中的内容，那么应该可以工作。所以对于那里提供的第一种方法的情况

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)

Answer 2

您可以将列表转换为 set() 组。示例：

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

您可以子集 a <= b 方法。工作顺利

Answer 3

直接命令式方法

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

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 对应外层 for 循环。

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]

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

How to check if a list (string) contains another list (string) considering order

python

string

list

sequence

python-3.x

直接命令式方法

函数方法