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

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，因此您永远不需要回溯。换句话说，如果有两个候选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| & |B| A分别是 Arrays和中存在的元素数B。因此，您得到线性复杂度。

Answer 3

正如@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 4

这是 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 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}))
}