时间戳

首页 > 解决方案 > 考虑顺序如何检查列表（字符串）是否包含另一个列表（字符串）

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

问题描述

我有两个列表（或字符串）：一个很大，另一个很小。我想检查较大的（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 in not A

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

案例 4. 错误，因为 A 中没有维护顺序 [2,1]，即使 A 包含 1 和 2。

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

A 和 B 可以是字符串。

标签： pythonpython-3.xstringlistsequence

解决方案

直接命令式方法

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

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 循环。

推荐阅读