你如何检查一个数组是否是另一个数组的子序列？

Question

我想探索不同的算法，包括递归和动态编程，检查一个 arrayA 是否是 arrayB 的子序列。例如，

arrayA = [1, 2, 3] 
arrayB = [5, 6, 1, 7, 2, 9, 3]

thus, arrayA is indeed a subsequence of arrayB.

我尝试了几种不同的搜索，但我似乎只能找到计算最长递增子序列的算法。

Answer 1

由于您必须将 arrayA 的所有元素匹配到 arrayB 的某些元素，因此您永远不需要 backtrack.换句话说，如果 arrayB 中有两个候选匹配 arrayA 中的一个元素，你可以选择最早的一个，并且永远不会撤回选择。

因此，你不需要DP，因为一个简单的线性贪婪策略就可以工作：

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;
}

Answer 2

正如 dasblinkenlight 所说的那样（我的措辞不能比他的回答更好！！）贪婪的方法绝对有效。您可以使用下面的伪代码（只是稍微解释一下，但与 dasblinkenlight 所写的完全相似）类似于两个排序数组的合并。

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*/

最坏情况下的时间复杂度为 O(|A|+|B|)，其中 |A| & |乙|分别是数组 A 和 B 中存在的元素数。因此你得到一个线性复杂度。

Answer 3

下面是 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

Answer 4

正如@sergey 前面提到的，这种情况下不需要回溯。这里只是问题的另一个 Python 版本：[时间复杂度：O(n) - 最差]


    >>> A = [1, 2, 3]
    >>> B = [5, 6, 1, 7, 8, 2, 4, 3]
    >>> def is_subsequence(A, B):
            it = iter(B)
            return all(x in it for x in A)
    
    >>> is_subsequence(A, B)
    True
    >>> is_subsequence([1, 3, 4], B)
    False
    >>>

Answer 5

这是GOLANG中的一个例子...

func subsequence(first, second []int) bool {
k := 0
for i := 0; i < len(first); i++ {
    j := k
    for ; j < len(second); j++ {
        if first[i] == second[j] {
            k = j + 1
            break
        }
    }
    if j == len(second) {
        return false
    }
}
return true
}

func main(){
      fmt.Println(subsequence([]int{1, 2, 3}, []int{5, 1, 3, 2, 4}))
}

你如何检查一个数组是否是另一个数组的子序列？

How do you check if one array is a subsequence of another?

algorithm

recursion

dynamic-programming

subsequence