如何验证一个字符串中的每个字符是否包含在另一个字符串中。就像 abc 是 string1，cbade 是 string2，string1（a b c） 中的所有字符都包含在 string2 中。实际上它看起来很简单，但我们需要最快的方法来做到这一点，所以仍然非常困难，我花了整整一周的时间无法得到一个解决方案。
如果您
使用的语言可以轻松地为字符分配数值（大多数语言），则可以使用查找表进一步加快速度：
- 查找表，每个字符一个插槽
- 在查找表中访问字符串 2 中的信件
- 确保访问字符串 1 中的字母
- ???
- 利润
长度： A + B
运行空间：A + B + N，其中 N 是可能的字符数。（C： 256， 爪哇： 65536）
如果不是，您应该能够在字符之间建立任意顺序，在这种情况下：
- 按字母顺序对两个字符串进行排序
- 二分搜索（您可以使用最后找到的匹配项的位置作为非常好的初始猜测）
- ???
- 利润
+ A*log（B）
运行空间：A + B
- 制作哈希映射（映射到布尔值的字符）
- 遍历 string1，在哈希表中为每个字符创建一个条目
- 迭代 string2，将哈希表中的条目设置为您看到的每个字符的 true
- 迭代哈希图中的元素（在我知道的大多数实现中可能，应该是 O（n），即 O（A）），如果您看到 false 条目，则停止并返回 false，否则返回 true
=>
时间：O（A+B），A 是字符串 1 的长度，B 是字符串 2 的长度
空间： O（A）假设：字符串/哈希图迭代：O（n） 时间，在哈希图中查找/插入：O（1） [注意这些可能都摊销了]
将两个字符串中的所有字符放入两组中，然后检查其中一个字符是否是另一个字符串的子集。在 Python 中：
>>> set("abc").issubset(set("cbade"))
True
你可以在 O（n） 中执行此操作。 首先构造第二个字符串中存在的字符的哈希表。 然后循环访问第一个字符串中的字符，并断言该字符在哈希表中有一个条目。
因为可能的字符数很小（假设 256），你可以有一个大小为 256 的固定数组，首先将其每个位设置为零，然后当你访问数组中第一个字符串集中相关位中的任何字符时，遍历第二个数组，如果你看到没有要设置的位， 意味着它们都在上一个字符串中，你可以说第二个字符串的所有字符在第一个字符串中都可用，否则，如果你在第二个字符串中看到一个字符，使得尚未设置相关位，你可以说第一个字符串不包含第二个字符串。该算法在时间上为 O（n），在存储器中为 O（1）（即 O（1） 外部存储器）。