python - 大海捞针，什么是更好的解决方案？

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) 的结果(因为你需要至少遍历字符串一次)。你可以做一些优化。

我假设你想匹配“whole words”，例如查找 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 module的地方派上用场，这将使您能够建立迷人的条件。例如正则表达式中的 \b 表示:

Matches the empty string, but only at the beginning or end of a word. A word is defined as a sequence of Unicode alphanumeric or underscore characters, so the end of a word is indicated by whitespace or a non-alphanumeric, non-underscore Unicode character. Note that formally, \b is defined as the boundary between a \w and a \W character (or vice versa), or between \w and the beginning/end of the string. This means that r'\bfoo\b' matches 'foo', 'foo.', '(foo)', 'bar foo baz' but not 'foobar' or '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()扫描字符串。基于文档:

Return an iterator yielding match objects over all non-overlapping matches for the RE pattern in string. The string is scanned left-to-right, and matches are returned in the order found. Empty matches are included in the result unless they touch the beginning of another match.

我假设匹配是即时生成的，因此它们永远不必立即存储在内存中(这对于大字符串可能会派上用场，有很多匹配项目)。最后数一下:

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