How do you check if one array is a subsequence of another?
I am looking to learn various algorithms, both recursive and dynamic programming, which checks if one array A is a subsequence of arrayB. For example,
arrayA = [1, 2, 3] arrayB = [5, 6, 1, 7, 2, 9, 3] thus, arrayA is indeed a subsequence of arrayB.
I've tried several different searches, but all I can find are algorithms to calculate the longest increasing subsequence.
source to share
Since you have to match all elements arrayA
to some elements arrayB
, you never need to return. In other words, if arrayB
there are two candidates to match an item arrayA
, you can choose the earliest one and never give up.
Hence, you don't need DP, because a simple linear greedy strategy will work:
bool isSubsequence(int[] arrayA, int[] arrayB) {
int startIndexB = 0;
foreach (int n in arrayA) {
int next = indexOf(arrayB, startIndexB , n);
if (next == NOT_FOUND) {
return false;
}
startIndexB = next+1;
}
return true;
}
source to share
As dasblinkenlight correctly said (and I couldn't formulate it better than his answer !!) the greedy approach works absolutely fine. You can use the following pseudocode (with a slightly more detailed explanation, but completely similar to what dasblinkenlight wrote), which is like merging two sorted arrays.
A = {..}
B = {..}
j = 0, k = 0
/*j and k are variables we use to traverse the arrays A and B respectively*/
for(j=0;j<A.size();){
/*We know that not all elements of A are present in B as we
have reached end of B and not all elements of A have been covered*/
if(k==B.size() && j<A.size()){
return false;
}
/*we increment the counters j and k both because we have found a match*/
else if(A[j]==B[k]){
j++,k++;
}
/*we increment k in the hope that next element may prove to be an element match*/
else if(A[j]!=B[k]){
k++;
}
}
return true; /*cause if we have reached this point of the code
we know that all elements of A are in B*/
Time complexity is O (| A | + | B |) worst case, where | A | and | B | - the number of elements present in the arrays A
and B
accordingly. This way you get linear complexity.
source to share
Here's an example in Ruby:
def sub_seq?(a_, b_)
arr_a = [a_,b_].max_by(&:length);
arr_b = [a_,b_].min_by(&:length);
arr_a.select.with_index do |a, index|
arr_a.index(a) &&
arr_b.index(a) &&
arr_b.index(a) <= arr_a.index(a)
end == arr_b
end
arrayA = [1, 2, 3]
arrayB = [5, 6, 1, 7, 2, 9, 3]
puts sub_seq?(arrayA, arrayB).inspect #=> true
source to share