Как я могу определить, содержится ли один список в другом, в том же порядке (на Java)?

Question

Предположим, у меня есть три списка:

list1 = a, c, d, r, t

list2 = a, d, t

list3 = a, r, d

Тогда list2 содержится в list1 , но list3 не потому, что он не в том же порядке.

Я проверял isSubCollection() из CollectionUtils в Apache Commons и метод 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();
}

Этот алгоритм является линейным и требует только 1 итерации в списке sup.

ОБНОВЛЕНИЕ
Если вы используете связанные списки, операция get может выполняться вНа).Таким образом, вы можете использовать 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;
} 

Но это выглядит ужаснее.

Answer 2

Требуемый здесь подход не зависит от языка, хотя, по крайней мере, вам нужно быть уверенным, что возможно для достижения вашей цели в Java.Решение проще описать с помощью указателей на языке C или C ++, но я попытаюсь использовать здесь более общие термины.

Начните с первого символа «содержащего списка»и «содержащийся список».

• Если два символа совпадают, переходите к следующему символу в обоих списках.

  • Если вы достигликонец «содержащегося списка», ответ «да», это , содержащийся в другом списке.

    В противном случае, если вы достигли конца «содержащего списка», ответнет, он не содержит «содержащийся список».

    В противном случае повторите процесс с двумя текущими символами.

• В противном случае перейдите к следующему символу «содержащего списка» и повторите попытку для того же символа «содержащегося списка».

  • Если вы достигли концаиз "содержащего списка" ответ - нет, он не содержит "содержащийсяlist. "

    В противном случае повторите процесс с двумя текущими символами.

Если нарисовать две стрелки (« указатели »)к символам в каждом списке на бумаге, и когда-либо поднимайте стрелку в «содержащем списке» справа, когда он соответствует символу в «содержащем списке», и поднимайте стрелку в «содержащем списке» справа на каждый шаг, вы увидите, как реализуются возможности для сопоставления успеха и неудачи.

Answer 3

Самостоятельно взбить не сложно.

boolean isSubSequence(List<?> sup, List<?> sub) {
  for (Object o : sub) {
    int index = sup.indexOf(o);
    if (index == -1) { return false; }
    sup = sup.subList(index + 1, sup.size());
  }
  return true;
}

Это занимает время O (sup.size () + sub.size ()), что в общем случае является оптимальным.

Answer 4

Не очень эффективно, но ...

Вы можете взять один элемент в списке list2 и повторять список list1, пока не найдете его или пока не достигнете конца списка.Если вы найдете его, сохраните индекс там, где вы его нашли.

Перейдите в list2 и выполните итерации list1 от первого индекса вперед.

Если вы дойдете до конца list2, этоподсписок по вашим критериям.

Если вы дошли до конца списка1 и еще не исчерпали список2, это не так.