擅长:python、mysql、java
<p>您可以先对前缀进行排序,这样就可以使用<code>bisect.bisect_left</code>方法在前缀中查找小于时间复杂度中给定单词的最近单词:</p>
<pre><code>from bisect import bisect_left
prefixes = sorted(prefixes)
def prefix(prefixes, word):
i = bisect_left(prefixes, word)
if i and word.startswith(prefixes[i - 1]):
return prefixes[i - 1]
raise ValueError("No prefix found for '%s'." % word)
</code></pre>
<p>以便:</p>
<pre><code>print(prefix(prefixes, 'non-word'))
print(prefix(prefixes, 'tele-video'))
print(prefix(prefixes, 'e-mail'))
</code></pre>
<p>输出:</p>
<pre><code>non-
tele-
e-
</code></pre>