我正在寻找探索递归和动态编程的不同算法，这些算法检查一个arrayA是否为arrayB的子序列。例如，
arrayA = [1, 2, 3]
arrayB = [5, 6, 1, 7, 2, 9, 3]
thus, arrayA is indeed a subsequence of arrayB.
我尝试了几种不同的搜索，但似乎只能找到计算最长增长子序列的算法。
由于必须将的所有元素匹配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;
}
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句