Function that checks if one array contains elements of another array but in order?

[1,2,3,4,5] -> [3,5] gives true
[1,2,3,4,5] -> [5,2] gives false

Is it possible to make the solution optimised?

CodePudding user response：

The solution is to step through the arrays in a staggered way. That way the complexity is O(n) rather than O(n²):

extension Sequence where Element: Equatable {
    func containsInOrder<S1>(_ arr: S1) -> Bool where S1: Sequence, S1.Element == Element {
        var it = makeIterator()
        var it1 = arr.makeIterator()
        var v = it.next()
        var v1 = it1.next()
        while v != nil, v1 != nil {
            if v == v1 {
                v1 = it1.next()
            }
            v = it.next()
        }
        return v1 == nil
    }
}

Use it like this:

[1,2,3,4,5].containsInOrder([3, 5])  // true
[1,2,3,4,5].containsInOrder([5, 3])  // false
"Hello World!".containsInOrder("HW") // true

Updated for Sequences...

CodePudding user response：

extension RandomAccessCollection where Self: RangeReplaceableCollection, Element: Equatable {
    func containsInOrder(other: Self) -> Bool {
        (self.isEmpty && other.isEmpty) ||
        containsInOrderWithoutEdgeCases(other: other) ||
            (self.last == other.last && containsInOrderWithoutEdgeCases(other: other.dropLast()))
    }
    
    private func containsInOrderWithoutEdgeCases<C: RandomAccessCollection>(other: C) -> Bool
        where C.Element == Element {
        other.reduce(self[...]) { acc, next in
            acc.drop(while: { $0 != next }).dropFirst()
        }.isEmpty == false
    }
}

Explanation

You could find each element of the second array in the first array by using something like

firstArray.drop(while: { $0 != target }).dropFirst()

This can then be fed into a reduce function, with the first array as the initial result. If the resulting array is not empty, then the first array contains the second array's elements in order.

extension RandomAccessCollection where Self: RangeReplaceableCollection, Element: Equatable {

   func containsInOrderWithoutEdgeCases<C: RandomAccessCollection>(other: C) -> Bool
        where C.Element == Element {
        other.reduce(self[...]) { acc, next in
            acc.drop(while: { $0 != next }).dropFirst()
        }.isEmpty == false
    }
}

Note that I used self[...] to get an SubSequence from self. The reduce works on SubSequences.

There are some edge cases not handled by this, so those need to be considered too. For example, cases when at least one of the arrays are empty.

The most interesting case is that, when the last element of the second array matches the last element of the first array. In this case, reduce would give an empty result even when the first array contains the elements of the second array, in order.

Therefore, if self.last == other.last, then the elements of other except last must also be contained in self, in order. Hence we arrive at the code at the top of the answer.

Test cases

[1,2,3,4,5].containsInOrder(other: [3, 4]) // true
[1,2,3,4,5].containsInOrder(other: [1, 4]) // true
[1,2,3,4,5].containsInOrder(other: [1]) // true
[1,2,3,4,5].containsInOrder(other: []) // true
[Int]().containsInOrder(other: []) // true
[Int]().containsInOrder(other: [1,2,3]) // false
[1,2,3,4,5].containsInOrder(other: [5,4,3]) // false
[1,2,3,4,5].containsInOrder(other: [4, 5]) // true
[1,2,3,4,5].containsInOrder(other: [7, 7, 7]) // false
[1,2,3,4,5].containsInOrder(other: [7, 5]) // false
[1,2,3,4, 5, 5].containsInOrder(other: [5, 5, 5]) // false

CodePudding user response：

You can think of AnyIterator as a "pauseable sequence", which can resume execution after an operation on an element.

extension Sequence where Element: Equatable {
  /// Whether this sequence contains all the elements of another, in order.
  func isOrderedSuperset<Elements: Sequence>(of elements: Elements) -> Bool
  where Elements.Element == Element {
    elements.allSatisfy(AnyIterator(makeIterator()).contains)
  }
}

XCTAssert([-10, 1, 2, 5, 2, 3, 0, 4, 6, 9, 5, 4].isOrderedSuperset(of: 1...5))
XCTAssert("