Problem statement

https://binarysearch.com/problems/Phone-Number-Combinations/

Solution

Equal to Leetcode 0017. Letter Combinations of a Phone Number.

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.

Code

class Solution:
    def solve(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])]