我在一次采访中被问到这个问题,如果你想知道一个字符串是否只由一组给定的字符组成。例如,让字符串集是{0,1,2,3,4,5,6,7,8,9}上的所有字符串,即所有"数字"字符串。其中,如果{3,8,5}上的字符串集仅为有效字符串,我如何检查该字符串是否仅由有效字符组成。说:
Input 8888338385
Output VALID
Input 887837348234
Output : Invalid
我建议的方法是暴力,需要根据无效字符列表检查给定字符串中的每个字符。如果其中任何一个字符无效,我会跳过检查所有其他字符并显示失败消息。然而,正如这里所建议的,可能还有更好的算法。请帮忙。
编辑:感谢Luc Touraille对原始算法的巨大改进。
创建布尔值的数组a[10]
。对于每个期望的数字e
,设置a[e] = true
。
现在,对于输入中的每个数字d
,检查a[d]
是否为真。如果不是,则返回false。如果他们都成功了,就返回真。
您可以使用256元素数组将其推广到所有ASCII字符。
如果您的输入字符串长度为N,比较字符串长度为M,字母表中的字母数为A,则复杂性为O(N+M)(扫描两个字符串)加O(A)(初始化布尔数组)。所以,除非你的字符串长度接近或大于你的字母表大小,否则这可能不是最佳的。
值得指出的是,关于Niklas Baumstark出色的性能比较,我们的两个解决方案实际上是相同的。这里构建的布尔数组与您在接受[c1c2…]*的两态DFA中构建的转换表完全相同。我想唯一的区别是Java的实现更通用,承载了更多的开销。
免责声明:根据我的假设,Java在优化这里使用的正则表达式方面似乎很糟糕,这会导致代码不合格。甚至Javascript的正则表达式似乎也比这更快。基准测试还表明Nick的解决方案非常快速。
这绝对是正则表达式的任务。在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();
}
}
对于c或c++,您可以执行以下操作:
const char* haystack = "8888338385";
const char* filter = "385";
if (strlen(haystack) != strspn(haystack, filter))
{
// oops - haystack contains more characters...
}
c++(std::string::find_first_not_of
)存在等价的std::string
函数
编辑:我意识到这是作弊,但问题中没有任何东西可以排除这一点。
您可以为允许集合中的每个字符使用映射(如果字母表的范围有限),并直接检查字符串中的每个字符串是否在映射中。这样,它只有O(N),其中N是字符串长度,而不是O(N*M),其中M是允许的字符集。如果字母表是大规模的,那么可以使用另一个数据结构来存储允许的字符-排序树,例如O(N)logN的复杂性。
我会首先对输入和无效字母列表进行排序,然后您总是可以确定字符串是否在线性时间中有效