c++ - 如何查找列表是否是另一个列表的子集？

Question

struct Node {
    int value;
    Node* next;
};

bool propSubset(Node* p, Node* q) {
    if(q == nullptr) return false;
    if(p == nullptr && q != nullptr) return true;
    if(p->value < q->value) return false;
    if(p->value > q->value) return propSubset(p, q->next);
    return propSubset(p->next, q->next);
}

p 是 q 的子集如果

• p的所有元素都是q的元素
• q至少有一个元素不在p中。

p和q都是升序排列

这就是我得到的全部，但它不适用于 p = {2, 4}, q = {1, 2, 3, 4}
我该如何改进呢？谢谢

Answer 1

迭代解决方案可能会更好。给定任意长度的列表，您不希望冒用完堆栈空间的风险。

由于 q 中的非交叉元素可以随机分布，因此大小因素也发挥了作用。

您可能想要重构您的代码，例如:

bool propSubset(Node* p, Node* q) {
  int len_q = length(q); // assuming you have length function.
  if (length(p) >= len_q) return false;

  for(int i=0; i < len_q && p != nullptr; ++i) {
    if (p->value == q->value) p = p->next;
    if (p->value < q->value) return false; // That particular value in p is not in q.
    q = q->next;
  }
  if (p == nullptr) return true;
  return false;
}