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

小编典典

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

algorithm

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

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

thus, arrayA is indeed a subsequence of arrayB.

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

阅读 401

2020-07-28

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

2020-07-28