问答

当前位置

amazon oa题目求解

  • by b
  • 2
  • 1 月,1 周前
  • Ta: 朱

刚刚做了亚麻的oa。题目比较简单。但是我居然第一题15个test cases只通过了5个。找了近一个小时,也没发现错在哪么。我把题目和我的解法贴出来,希望大家指教。

题目:给一个list,其中存了n个不同的string。现在用户type一个query。要求动态的输出每次用户type一个char,返回当前type的query能够match哪些list中的string。(1) 如果有超过3个string能够match当前的query,那么最多只返回3个。(2) 返回matched strings要按alpha order排列。

我的解法就是直接用hashmap。感觉非常简单啊。不知道哪儿出错了。

input: dict - list of string; query - user query
def f(dict, query):
if not query:
return []

dict.sort()
hashmap = collections.defaultdict(list)
for w in dict:
    for i in xrange(len(w)):
        hashmap[w[:i + 1]].append(w)

res = []
for i in xrange(len(query)):
    q = query[:i + 1]
    tmp = hashmap[q]
    res.append(tmp[:3])

return res

2 个回复

2019-09-13 邓同学

这个看上去应该用 Trie 做啊 word search


2019-09-13 b

阿西巴。。。。我知道我哪儿错了。题目说search是case insensitive,我做的时候不知道哪跟筋没对,自动翻译成了case sensitive。。。。。

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1