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

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

由于必须匹配某些元素的所有元素,因此您永远不需要回溯.换句话说,如果有两个候选者匹配一个元素,你可以选择最早的一个,而不是撤回选择.arrayAarrayBarrayBarrayA

因此,您不需要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;
}