c++ - 找出字符串是否仅包含给定字符集的最佳方法/算法

Question

我在一次采访中被问到这个问题，如果您要找出一个字符串是否仅由一组给定的字符组成。例如，让字符串集是 {0,1,2,3,4,5,6,7,8,9} 上的所有字符串，即所有“数字”字符串。其中，如果超过 {3,8,5} 的字符串集只是有效的，我如何检查字符串是否只包含有效字符。说:

Input 8888338385
     Output VALID
Input 887837348234 
Output : Invalid

我建议的方法是蛮力，需要根据无效字符列表检查给定字符串中的每个字符。如果任何一个字符无效，我会跳过检查所有其他字符并显示失败消息。但是，正如建议的 here ，可能会有更好的算法。请帮忙。

Answer 1

编辑:感谢 Luc Touraille 对原始算法的巨大改进。

创建一个 bool 数组a[10]。对于每个预期的数字 e，设置 a[e] = true。

现在对于输入中的每个数字 d，检查 a[d] 是否为真。如果不是，则返回 false。如果都成功，则返回 true。

您可以将其推广到具有 256 个元素的数组的所有 ASCII 字符。

如果您的输入字符串长度为 N，您的比较字符串长度为 M，并且字母表中的字母数为 A，那么复杂度为 O(N+M)(扫描您的两个字符串)加上 O(A )(初始化 bool 数组)。因此，除非您的字符串长度接近或大于您的字母大小，否则这可能不是最佳选择。

值得指出的是，关于 Niklas Baumstark 出色的 performance comparison ，我们的两个解决方案实际上是相同的。这里构造的 bool 数组相同 与您将在两个状态下构建的转换表 DFA接受 [c₁c₂...]*。我想唯一的区别是 Java 的实现更加通用，需要更多的开销。