Leetcode 17. Letter Combinations of a Phone Number

Problem

Leetcode 17 - Letter Combinations of a Phone Number

Example:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Input: digits = ""
Output: []

Input: digits = "2"
Output: ["a","b","c"]

Approach

Using DFS and map for each digit to string, we can solve this problem. Similar to permutation problem.

Here is the Python code for the solution:

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        num_to_string = {
            2 : ['a', 'b', 'c'],
            3 : ['d', 'e', 'f'],
            4 : ['g', 'h', 'i'],
            5 : ['j', 'k', 'l'],
            6 : ['m', 'n', 'o'],
            7 : ['p', 'q', 'r', 's'],
            8 : ['t', 'u', 'v'],
            9 : ['w', 'x', 'y', 'z']
        }

        res = []

        def dfs(i, arr):
            if i == len(digits):
                res.append(''.join(arr.copy()))
                return
            
            dig = digits[i]
            for j in range(len(num_to_string[dig])):
                arr.append(num_to_string[dig][j])
                dfs(i+1, arr)
                arr.pop()
            
        if len(digits) == 0:
            return res
        dfs(0, [])
        return res    

Time Complexity and Space Complexity

Time Complexity: $O(n*4^n)$

Space Complexity: $O(n*4^n)$