Leetcode 0017. Letter Combinations of a Phone Number

Problem statement

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

Solution

One way to solve this problem is to do backtracking. However we can use functionality of python product function, which will do almost everything for us. What is product? It is casterian product of two objects, for example if we have ob1 = [a, b, c] and ob2 = [d, e], then product(ob1, ob2) = [ad, bd, cd, ae, be, ce]. And this is almost what we need:

1. In fact what will be returned are lists, so we need to join them.
2. We need product of not 2 but several objects, and we will use * notation for this.

Complexity

Both time and space is O(3^m*4^n*(m+n)), where m is number of digits for which we have 3 options and n is number of letters for which we have 4 options, because we have 3^m*4^n options with m+n length each.

class Solution:
    def letterCombinations(self, digits):
        if not digits: return []
        d = {"2":"abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno", "7":"pqrs", "8":"tuv", "9":"wxyz"}
        return ["".join(num) for num in product(*[d[i] for i in digits])]