string - 通过将字符串 B 的子序列附加到空字符串 C 来创建字符串 A 所需的最少操作数

Question

您已经给出了两个字符串 A 和 B。您有一些空字符串 C。在一次操作中您可以从字符串 B 中删除任何字符（从任何地方）并将其附加到字符串 C。将字符串 C 转换为所需的最少操作数字符串 A。

例如，如果 A 是“ABCDE”而 B 是“ABDEC”，那么在第一个操作中，您将从 B 中选择子序列 ABC，在第二个操作中选择 DE。

所以需要两个操作。

如果 A 是“ABCDE” B 是“EDCBA”，则需要操作 5。

预期线性复杂度 O(n)

标签： stringalgorithmdata-structures

Answer 1

只需使用贪心算法。

1 - 让i = 0
2 - 让3 -在4之后j = 0
搜索第一个 - 如果它存在，让它成为它的索引，从 中删除，附加到，递增，然后从 3 开始重复 5 - 如果不存在，重复从 2A[i]Bj
jBBCi

每次达到 5 对应一个操作。

假设A( 和B) 的所有字符都不同，那么这里有一个线性复杂度的解。您需要一个哈希图或类似的东西，以及一个与和Y等长的索引数组。AB

1 - 将哈希图中的每个字符A作为键，其索引作为值。
2-查找B哈希图中的每个字符以获取值i，并将其索引放入Y该位置i。
3-通过Y计算次数Y[i] < Y[i-1]。那是您的操作次数。