Given two arrays of numbers, how to check if the first sequence is a sub sequence of second sequence.
For example [3, 7, 11] is a sub-sequence of [9, 3, 1, 7, 5, 11]
where as [4, 8, 9] is not a sub-sequence of [6, 4, 9, 2, 8]
The algorithm here is simple.
For example [3, 7, 11] is a sub-sequence of [9, 3, 1, 7, 5, 11]
where as [4, 8, 9] is not a sub-sequence of [6, 4, 9, 2, 8]
The algorithm here is simple.
- Let us assume two indices i, j point to the beginning of sub-sequence and sequence respectively.
- Do the following until we reach the end of any sequence.
- If both the elements are same, increment both indices.
- Otherwise increment j only.
At the end of this iteration, if we have seen all the elements of sub-sequence in the given sequence, we are done! otherwise we have not found!
Here is the code in C++ which implements the above approach. This runs in O(n) time and O(1) space. For Python code click here. For Java code click here.