How do you check if one array is a subsequence of

问题:

I'm looking to explore different algorithms, both recursive and dynamic programming, that checks if one arrayA 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 a few different searches, but all I can seem to find is algorithms to compute the longest increasing subsequence.

回答1:

Since you must match all elements of arrayA to some elements of arrayB, you never need to backtrack. In other words, if there are two candidates in arrayB to match an element of arrayA, you can pick the earliest one, and never retract the choice.

Therefore, you do not need DP, because a straightforward 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;
}

回答2:

As dasblinkenlight has correctly said(and i could not have phrased it better than his answer!!) a greedy approach works absolutely fine. You could use the following pseudocode (with just a little more explanation but totally similar to what dasblinkenlight has written)which is similar to the merging of 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|) in the worst case, where |A| & |B| are the number of elements present in Arrays A and B respectively. Thus you get a linear complexity.

回答3:

Here is 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

回答4:

And here's a python example:

def is_sublist(a,b):
    idx_b = 0
    for v in a:
        try:
            b[idx_b:].index(v)
        except ValueError:
            return False
        idx_b += 1
    return True