java - 如何确定一个列表是否以相同的顺序包含在另一个列表中(在 Java 中)？

Question

假设我有三个列表:

list1 = a, c, d, r, t

list2 = a, d, t

list3 = a, r, d

然后 list2 包含在 list1 中，但 list3 不包含，因为它的顺序不同。

我检查了 Apache Commons 中 CollectionUtils 中的 isSubCollection() 和 containsAll() 方法，但似乎它们没有考虑顺序。

Answer 1

boolean isSubsequence(List<?> sup, List<?> sub) {
    int current = 0;
    for (Object obj: sup) {
      if (current == sub.size()) {
         return true;
      }
      if (obj.equals(sub.get(current)) {
        current++;
      }
    }
    return current == sub.size();
}

该算法是线性的，仅需要在 sup 列表中进行 1 次迭代。

更新
如果您使用链表，get 操作的运行时间可能为 O(n)。所以你可以使用2个迭代器:

boolean isSubsequence(List<?> sup, List<?> sub) {
  Iterator<?> supIt = sup.iterator();
  for (Iterator<?> subIt = sub.iterator(); subIt.hasNext();) {
    Object current = subIt.next();
    boolean found = false;
    while (supIt.hasNext() && !found) {
      found |= supIt.next().equals(current);
    }
    if (!found) {
      return false;
    }
  }
  return true;
} 

但是看起来更丑了。