擅长:python、mysql、java
<p>这是<a href="https://stackoverflow.com/a/47260660/1222951">PM 2Ring's solution</a>的一个稍微高效的版本,用循环替换对<code>product</code>的调用:</p>
<pre><code>from itertools import product
def words_range(src, query):
query = set(query)
# Create a dict to store the word positions in src of each query word
pos = {s: [] for s in query}
for i, s in enumerate(src):
if s in pos:
pos[s].append(i)
# Find all the ranges that hold all the query word
# We'll iterate over the input string and keep track of
# where each word appeared last
last_pos = {}
ranges = []
for i, word in enumerate(src):
if word in query:
last_pos[word] = i
if len(last_pos) == len(query):
ranges.append( (min(last_pos.values()), i) )
# Find the smallest range
return min(ranges, key=lambda t:t[1] - t[0])
</code></pre>
<p>它不是完全线性的时间(因为循环中有<code>min(last_pos.values())</code>),但它是朝着正确方向迈出的一步。可能有一种方法可以去掉<code>min</code>调用(我现在想不起来),这会使这个函数线性化。你知道吗</p>