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

Question

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

песни1 = а, C, D, R, T

песни2 = а, D, Т

песни3 = а, r, d

Затем list2 is contai ned in 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.

UPDATE
При использовании связанных списков, 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; 
} 

Но это выглядит уродливым.

Answer 2

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

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

Продвиньтесь в списке2 и переместите список1 с первого указателя вперед.

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

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

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

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

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

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

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

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

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

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

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

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

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