我有一个字符串S(单词索引从0开始)和一个子字符串Q。我希望在S中找到包含Q中所有单词的最小范围[L,R]。Q中没有重复的单词。我该如何处理这个问题?你知道吗
例如
输入:S:那只懒洋洋的棕色狐狸跳到另一只棕色狐狸身上,那只懒洋洋的狗吃了狐狸的食物,那它怎么办 Q:懒惰的棕色狗
输出:[11,15]
我的代码:
S = raw_input().strip().split(' ')
Q = raw_input().strip().split(' ')
count = [0 for x in range(len(Q))]
smallest_index = [0 for x in range(len(Q))]
largest_index = [0 for x in range(len(Q))]
for i in range(len(S)):
for j in range(len(Q)):
if S[i] == Q[j]:
count[j] += 1
if count[j] <= 1:
smallest_index[j] = i
largest_index[j] = i
if count[j] > 1:
largest_index[j] = i
largest_index.sort()
print "[%d," % largest_index[0],
print "%d]" % largest_index[len(Q)-1]
这是PM 2Ring's solution的一个稍微高效的版本,用循环替换对
product
的调用:它不是完全线性的时间(因为循环中有
min(last_pos.values())
),但它是朝着正确方向迈出的一步。可能有一种方法可以去掉min
调用(我现在想不起来),这会使这个函数线性化。你知道吗这段代码不是特别有效,但确实可以正常工作。也许有人会想出比使用
product
更好的方法来处理位置信息。同时,您可以使用此代码对其他算法进行测试。你知道吗输出
以下是另一种基于@pm2ring答案的方法:
输出:
相关问题 更多 >
编程相关推荐