查找字符串是否仅包含给定字符集的最佳方法/算法

Question

我在接受采访时被问到这个问题,如果你要找出一个字符串是否只包含一组给定的字符.例如,让字符串集成为{0,1,2,3,4,5,6,7,8,9}上的所有字符串,即所有"数字"字符串.其中,如果{3,8,5}上的字符串集只是有效字符串,如何检查该字符串是否仅包含有效字符.说:

Input 8888338385
     Output VALID
Input 887837348234 
Output : Invalid

我建议的方式是暴力,需要检查给定字符串中的每个字符与无效字符列表.如果任何一个字符无效,我将跳过检查所有其他字符并显示失败消息.但是,如此处所示,可能有更好的算法.请帮忙.

Answer 1

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

创建一个a[10]布尔数组.对于每个预期的数字e,设置a[e] = true.

现在,对于d输入中的每个数字,检查是否a[d]为真.如果不是,则返回false.如果他们都成功了,那就回归真实.

您可以将此概括为具有256个元素数组的所有ASCII字符.

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

值得指出的是,就Niklas Baumstark的出色性能比较而言,我们的两种解决方案实际上是相同的.这里构造的布尔数组与您在双状态DFA中构建的转换表相同 [c ₁ c ₂ ...]*.我想,唯一的区别是Java的实现更加通用,会带来更多的开销.

Answer 2

免责声明:反对我的假设,爪哇好像吸在优化这里使用的正则表达式,从而导致unperformant代码.即使Javascript的正则表达式似乎比这更快.基准测试还显示尼克的解决方案非常快.

这绝对是正则表达式的任务.在Java中:

public boolean isValidString(String str) {
  return str.matches("[358]*");
}

这应该是O(n)最糟糕的情况,并且不能比这更好,因为每个角色都必须被看待.

如果性能至关重要,您可能希望缓存预编译的模式匹配器:

import java.util.regex.Pattern;

public class Matcher {
  private Pattern pattern;

  public Matcher() {
    this.pattern = Pattern.compile("[358]*");
  }

  public isValid(String str) {
    return pattern.matcher(str).matches();
  }
}