Как я могу проверить, является ли вектор подпоследовательностью (в том же порядке, но не смежной) другого вектора? - PullRequest
Новая
       22

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

3 голосов
/ 01 апреля 2020

Как я могу проверить, все ли элементы vector_a также отображаются в том же порядке, что и vector_b?

vector_b может быть очень длинным, нет предположения, что он отсортирован, но это не имеет повторяющихся элементов.

Я не смог найти метод, реализованный для Vec или в itertools, поэтому я попытался реализовать, выполнив:

  1. Создайте хэш-карту из vector_b отображение value -> index
  2. Выполните итерацию по vector_b и убедитесь, что:
    • Элемент существует в хэш-карте
    • Индекс строго больше индекса предыдущего элемента

Я не очень доволен этим, так как это не экономит место из-за создания hashmap.

Ответы [ 2 ]

6 голосов
/ 01 апреля 2020

Поиск каждого элемента иголки в стоге сена по порядку. Каждый раз, когда вы найдете соответствующий элемент, продолжайте поиск только в оставшейся части стога сена. Вы можете express это красиво сделать, взяв новый подрезок стога сена каждый раз, когда вы сопоставляете элемент. 

fn is_subsequence<T: PartialEq>(needle: &[T], mut haystack: &[T]) -> bool {
    for search in needle {
        if let Some(index) = haystack.iter().position(|el| search == el) {
            haystack = &haystack[index + 1..];
        } else {
            return false;
        }
    }
    true
}

assert!(is_subsequence(b"", b"0123456789"));
assert!(is_subsequence(b"0", b"0123456789"));
assert!(is_subsequence(b"059", b"0123456789"));
assert!(is_subsequence(b"345", b"0123456789"));
assert!(is_subsequence(b"0123456789", b"0123456789"));

assert!(!is_subsequence(b"335", b"0123456789"));
assert!(!is_subsequence(b"543", b"0123456789"));

Срез - это просто указатель и размер, хранящиеся в стеке, так что это нет новых распределений. Он запускается за O(n) времени и должен быть близок к максимально быстрой реализации - или, по крайней мере, на том же этапе.

4 голосов
/ 01 апреля 2020

Самый простой способ сделать это - перебрать два вектора вместе: 

fn contains<T: PartialEq>(needle: &[T], haystack: &[T]) -> bool {
    let mut idx = 0;
    for it in needle {
        while (idx < haystack.len()) && (&haystack[idx] != it) {
            idx += 1;
        }
        if idx == haystack.len() {
            return false;
        }
    }
    return true;
}
...