2

This is a common interview question and I know there are already loads of questions about it, but none that really help me, so here goes. The question is as follows:

Given a digit string, return all possible letter combinations that the number could represent if entered on a standard phone number pad.

Input: "23"

Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

I've written a basic, iterative (non-recursive) solution in python which seems to work:

letters = {
    '1': '',
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz',
    '0': ''
}

def combinations(number_string):

    output = []

    for index, number in enumerate(number_string):
        
        temp_list = []
        for letter in letters[number]:
            if not letters:
                continue

            if index == 0:
                output.append(letter)
            else:
                for combo in output:
                    temp_list.append(combo + letter)

        if temp_list:
             output = temp_list
           
    return output

print(combinations('234'))

But what is the time complexity and why?

I understand that I am iterating through each element in the input string, which gives us at least O(n) right away.

Then for each of those elements, I am iterating through up to 4 possible letter combinations, so I understand that gets us to O(4n).

But for each of the letter combinations, I am then iterating over all the combinations already obtained (to modify each for the latest letter). This is where I get lost.

pkenrick
  • 41
  • 5
  • 1
    It's `O(4^n)` not `O(4n)`. Imagine the question was: given a number of digits in decimal, print all the numbers. If the digit was 3, you'd say `10^3`, or `10*10*10`. if it was 5, you'd say `10^5`. Here the answer is `O(10^n)`. In this case if we have the letters say, `6,7,8` the total permutations is `3*4*3`. If we didn't know which three numbers we would be passed, then our answer would be the worst case, `4*4*4` or `O(4^n)` – flakes Mar 17 '21 at 20:27
  • Voting to reopen. I don't think it's appropriate to close arbitrary time complexity questions against a canonical that basically doesn't answer the question or even offer the tools to do so. I'm pretty sure OP knows about nested loop complexity as the dupe shows. – ggorlen Mar 17 '21 at 20:28
  • flakes is correct, but even if you're not sure, you can derive the formula here by printing out the length of output on the worst case `"7"`, `"77"`, `"777"`... for every length `n` up to 10 or so, then look at the pattern. 0, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144... BTW, `if not letters: continue` is basically always true and can be removed. – ggorlen Mar 17 '21 at 20:31
  • @ggorlen Ignoring the costs of building the strings and calling this "permutations"... I wouldn't call that "totally correct". – Manuel Mar 17 '21 at 20:33
  • @Manuel Good points, thanks for pointing that out. Building the strings can be done in linear time and is sort of an implementation detail as far as I'm concerned, you can easily change `+` to `append` and use lists to avoid Schlemiel the Painter's algorithm. Yes, it's a Cartesian product, not a permutation. – ggorlen Mar 17 '21 at 20:35

0 Answers0