I'm writing a function that takes a number (eg, 2345) and selects those names from a pre-defined list of names (in a text file) that can be formed by replacing each number with one of three corresponding letters, shown below:
2: ['A', 'B', 'C']
3: ['D', 'E', 'F']
4: ['G', 'H', 'I']
5: ['J', 'K', 'L']
6: ['M', 'N', 'O']
7: ['P', 'R', 'S']
8: ['T', 'U', 'V']
9: ['W', 'X', 'Y']
I wrote a recursive function to create a list of all possible combinations of letters, then select those that match up to names in the pre-defined list of names. This worked but was extremely slow for longer numbers (up to 12 digits). I figure (although I may be wrong) that such an algorithm would be O(3^n) -- Is that correct?
# works, but slow
def lettercombos(num):
if (len(num) == 1):
return numdict[int(num)]
for n in num:
ret = []
for l in numdict[int(n)]:
for x in lettercombos(num[1:]):
ret.append(l + x)
return ret
My next approach was to first remove all names from the list that were not the same length as the number. Then, I iterate through each digit of the number, and remove names from the new list of names that do not have the corresponding letters for that number in that location. I ended up writing the following code:
# does not work
for i in range(len(num)):
letters = numdict[int(num[i])]
for name in namelist:
if name[i] not in letters:
namelist.remove(name)
However, this does not work properly. I cannot figure out what is going wrong. Am I using the list.remove() function correctly? I can't seem to figure out what the problem could be.
Thanks for your help.