algorithm - 一个字符串中的字符包含在另一个字符串中

Question

如何验证一个字符串中的每个字符都包含在另一个字符串中。比如，abc 是 string1，cbade 是 string2，string1(abc) 中的所有字符都包含在 string2 中。实际上它看起来很简单，但我们需要最快的方法来做到这一点，所以仍然非常困难，我花了整整一周的时间都找不到一个解决方案。

Answer 1

如果您使用的语言可以轻松地为字符分配数值（大多数语言），则可以使用查找表进一步加快速度：

1. 查找表，每个字符一个槽
2. 访问查找表中 string2 中的字母
3. 确保 string1 中的字母被访问
4. ？？？
5. 利润

运行时：A + B 运行
空间：A + B + N，其中 N 是可能的字符数。（C：256，Java：65536）

如果不是，您应该能够在字符之间建立任意顺序，在这种情况下：

1. 按字母顺序对两个字符串进行排序
2. 二分搜索（您可以使用最后找到的匹配的位置作为一个非常好的初始猜测）
3. ？？？
4. 利润

运行时：A*log(A) + B*log(B) + A*log(B)
运行空间：A + B

Answer 2

1. 制作哈希映射（映射到布尔值的字符）
2. 遍历 string1，在哈希表中为每个字符创建一个条目
3. 遍历 string2，将哈希表中的条目设置为您看到的每个字符的 true
4. 遍历哈希映射中的元素（可能在我知道的大多数实现中，应该是 O(n)，即 O(A)），如果看到错误条目，则停止并返回 false，否则返回 true
   =>
   Time: O(A +B), A 是 string1 的长度，B 是 string2 的
   空间：O(A)
   
   假设：迭代字符串/hashmap：O(n) 时间，在 hashmap 中查找/插入：O(1) [注意这些可能都是摊销]

Answer 3

将两个字符串中的所有字符分成两组，然后检查一个是另一个的子集。在 Python 中：

>>> set("abc").issubset(set("cbade"))
True

Answer 4

您可以在 O(n) 中执行此操作。首先构造第二个字符串中存在的字符的哈希表。然后遍历第一个字符串中的字符并断言该字符在哈希表中有一个条目。

Answer 5

因为可能的字符数很小（假设为 256），所以您可以有一个大小为 256 的固定数组，首先将其每个位设置为零，然后当您访问第一个字符串中的任何字符时，请在数组中设置相关位，之后遍历第二个数组，如果你看到没有要设置的位，意味着它们都在前一个字符串中，你可以说第二个字符串的所有字符都在第一个字符串中可用，否则，如果你在第二个字符串中看到一个字符，使得相关位尚未设置，您可以说第一个字符串不包含第二个字符串。该算法在时间上为 O(n)，在内存中为 O(1)（即 O(1) 外部存储器）。