Organisation of the function
You are doing many things in the same function which make the whole thing a bit confusing. First thing to do is to split the two main parts of the functions : one does preprocessing on usernames, one handles queries. One this is done, your code looks like :
def typeahead(usernames, queries):
# Pre-processing on usernames
username_lower = [item.lower() for item in usernames]
username_lower = sorted(username_lower)
alphabet = [[] for x in xrange(26)]
myDict = {'a':0,'b':1,'c':2,'d':3,'e':4,'f':5,'g':6,'h':7,'i':8,'j':9,'k':10,'l':11,'m':12,'n':13,'o':14,'p':15,'q':16,'r':17,'s':18,'t':19,'u':20,'v':21,'w':22,'x':23,'y':24,'z':25}
[alphabet[myDict[username[0]]].append(username) for username in username_lower]
# Handling the queries
matches=[]
amount_of_queries = len(queries)
results = [-1]*amount_of_queries
queries_lower = [query.lower() for query in queries]
querylen = [len(query) for query in queries]
for q in xrange(amount_of_queries):
matches[:] = []
quer = queries_lower[q]
if querylen[q]==1:
results[q] = alphabet[myDict[quer[0]]][0]
else:
matches = [item for item in alphabet[myDict[quer[0]]] if quer==item[:querylen[q]]]
if len(matches)>=1:
results[q]= matches[0]
print '\n'.join(map(str, results))
Before we go any further, something to keep in mind
I am not quite sure that this is an issue but in your example, your print lower-case usernames even though usernames with their original case is printed on this original problem.
Making your map from letters to username a bit cleaner
At the moment, you always use alphabet and myDict together. This is a good sign that something is wrong. (Also, if you really want to map letters to their index, you don't need dictionnary with hardcoded value, you just need arithmetic, ord/chr). If what you want is just to match letters with the list of corresponding usernames, you can use normal dictionnary and check if items are already present, normal dictionnary and fill with empty list from the very beginning or you could play it smart and use Python good stuff as defaultdict and setdefault :
from collections import defaultdict
mapping = defaultdict(list)
mapping2 = dict()
for username in usernames:
low = username.lower()
mapping[low[0]].append(low)
mapping2.setdefault(low[0], []).append(low)
I'll assume we are using the defaultdict option from now.
In order to integrate this part of the solution in your code, let's remove the duplicated code from what we have in the part handling the queries :
for q in xrange(amount_of_queries):
matches[:] = []
quer = queries_lower[q]
candidates = alphabet[myDict[quer[0]]] ### THIS IS WHAT IS HAVE ADDED
if querylen[q]==1:
results[q] = candidates[0]
else:
matches = [item for item in candidates if quer==item[:querylen[q]]]
if len(matches)>=1:
results[q]= matches[0]
Replacing this with our defaultdict logic, we get :
def typeahead(usernames, queries):
# Pre-processing on usernames
mapping = defaultdict(list)
for username in usernames:
mapping[username.lower()[0]].append(username.lower())
# Handling the queries
matches=[]
amount_of_queries = len(queries)
results = [-1]*amount_of_queries
queries_lower = [query.lower() for query in queries]
querylen = [len(query) for query in queries]
for q in xrange(amount_of_queries):
matches[:] = []
quer = queries_lower[q]
candidates = mapping[quer[0]]
if querylen[q]==1:
results[q] = candidates[0]
else:
matches = [item for item in candidates if quer==item[:querylen[q]]]
if len(matches)>=1:
results[q]= matches[0]
print '\n'.join(map(str, results))
Please note that I took this chance to remove the list you were building with a useless list-comprehension.
Handling the queries
As you are about to iterate on queries anyway, there's no real need to build lists with information you will need. You can just iterate over queries and that will do the trick.
Also, you can initialise matches inside the loop and use enumerate if you really need the index. At this point, the part of the code looks like :
# Handling the queries
results = [-1]*len(queries)
for i,q in enumerate(queries):
matches=[]
low_quer = q.lower()
l = len(low_quer)
candidates = mapping[low_quer[0]]
if l==1:
results[i] = candidates[0]
else:
matches = [item for item in candidates if low_quer==item[:l]]
if len(matches)>=1:
results[i]= matches[0]
Finally, we don't even need the indices as we can build results as we go. Also, we don't need matches in that part of the function. Things get even more concise :
# Handling the queries
results = []
for q in queries:
low_quer = q.lower()
l = len(low_quer)
candidates = mapping[low_quer[0]]
if l==1:
results.append(candidates[0])
else:
matches = [item for item in candidates if low_quer==item[:l]]
if len(matches)>=1:
results.append(matches[0])
else:
results.append('-1')
Another issue found
What if we look for "c" ? At the moment, we'll do results.append(candidates[0]) with an empty list of candidates : this will crash. This should be handled much the same way we do for longer strings : check if we do have a match. Also, this removes some unrequired logic :
# Handling the queries
results = []
for q in queries:
low_quer = q.lower()
l = len(low_quer)
matches = [item for item in mapping[low_quer[0]] if low_quer==item[:l]]
if len(matches)>=1:
results.append(matches[0])
else:
results.append('-1')
If we want to play it cool, we can use the fact that in a boolean context, an empty list is considered False while a non-empty list is considered True. Also, we can use the ternary operator. Finally, because I am now using the string -1 and not the integer, we don't need the conversion to string at the end. We get :
# Handling the queries
results = []
for q in queries:
low_quer = q.lower()
l = len(low_quer)
matches = [item for item in mapping[low_quer[0]] if low_quer==item[:l]]
results.append(matches[0] if matches else '-1')
print '\n'.join(results)
Using the right function
Using startswith you don't need to do some tricky string handling :
# Handling the queries
results = []
for q in queries:
q = q.lower()
matches = [item for item in mapping[q[0]] if item.startswith(q)]
results.append(matches[0] if matches else '-1')
Your final code becomes :
def typeahead(usernames, queries):
# Pre-processing on usernames
mapping = defaultdict(list)
for username in usernames:
low = username.lower()
mapping[low[0]].append(low)
print mapping
# Handling the queries
results = []
for q in queries:
q = q.lower()
matches = [item for item in mapping[q[0]] if item.startswith(q)]
results.append(matches[0] if matches else '-1')
print '\n'.join(results)
A few things are not perfect yet : the fact that we get the lower-case name, the fact that we haven't sorted the values but I'll let your play with this.
And now for something different
The trick you have used to map first letter to potential candidates makes things at most 26 times faster. In real life, this performance boost will not be that huge because usernames are not uniform over the alphabet. You might want to generalise this trick over all letters of the words. Here are a few pages that you might find interesting :
