如何检查一个数组是否是另一个数组的子序列？ [英] How do you check if one array is a subsequence of another?

问题描述

我正在寻求探索递归和动态编程的不同算法，这些算法可以检查一个arrayA是否为arrayB的子序列。例如，

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.

推荐答案

因为必须匹配 arrayA all 个元素$ c>到 arrayB 的某些元素，则无需回溯。换句话说，如果 arrayB 中有两个候选者匹配 arrayA 的元素，则可以选择最早的一个，而且永远不要撤消选择。

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.

因此，您不需要DP，因为一种简单的线性贪心策略会起作用：

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

这篇关于如何检查一个数组是否是另一个数组的子序列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！