在大海捞针找到针,什么是更好的解决方案？

Question

所以给了"针"和"这里有针但不是这个针干草堆"

我写

def find_needle(n,h):
    count = 0
    words = h.split(" ")
    for word in words:
        if word == n:
            count += 1
    return count

这是O(n),但想知道是否有更好的方法？也许不是通过使用拆分？

您将如何为此案例编写测试以检查它是否处理所有边缘情况？

Answer 1

我认为不可能O(n)对此感到沮丧(因为你需要至少迭代一次字符串).你可以做一些优化.

我假设您想要匹配" 整个单词 ",例如查找foo应该匹配如下:

foo and foo, or foobar and not foo.
^^^     ^^^                    ^^^

因此,基于空间的夹板不会起作用,因为:

>>> 'foo and foo, or foobar and not foo.'.split(' ')
['foo', 'and', 'foo,', 'or', 'foobar', 'and', 'not', 'foo.']
#                  ^                                     ^

这是re模块派上用场的地方,这将使您能够构建迷人的条件.例如,\b在正则表达式内部意味着:

匹配空字符串,但仅匹配单词的开头或结尾.单词被定义为Unicode字母数字或下划线字符的序列,因此单词的结尾由空格或非字母数字的非下划线Unicode字符表示.注意,正式地,\b定义为a \w和\W字符之间的边界(反之亦然),或者在\w字符串的开头/结尾之间.这意味着,r'\bfoo\b'比赛'foo','foo.','(foo)','bar foo baz'但不'foobar'还是'foo3'.

所以r'\bfoo\b'只匹配整个单词foo.另外别忘了使用re.escape():

>>> re.escape('foo.bar+')
'foo\\.bar\\+'
>>> r'\b{}\b'.format(re.escape('foo.bar+'))
'\\bfoo\\.bar\\+\\b'

您现在要做的就是re.finditer()用来扫描字符串.根据文件:

返回一个迭代器,在字符串中的RE模式的所有非重叠匹配上产生匹配对象.从左到右扫描字符串,并按找到的顺序返回匹配项.结果中包含空匹配,除非它们触及另一个匹配的开头.

我假设匹配是在运行中生成的,因此它们不必一次在内存中(对于大字符串,可能会派上用场,并且有很多匹配的项目).最后只计算它们:

>>> r = re.compile(r'\bfoo\b')
>>> it = r.finditer('foo and foo, or foobar and not foo.')
>>> sum(1 for _ in it)
3

Answer 2

这不解决复杂性问题,但简化了代码:

def find_needle(n,h):
    return h.split().count(n)