LeetCode 17: Letter Combinations of a Phone Number ·

Table of Contents

Meta Data
#

Difficulty: medium First Attempt: 2022-10-20

Submissions: Runtime Error ×8 → Accepted → Runtime Error → Accepted ×2

Approach
#

Level i handles digits[i], appending each of its letters to the current string, and records once every digit is handled (Backtracking template). An empty digits returns [], not [""].

My Attempts
#

This took 12 submissions, nearly all Python scoping:

The recursion lived in another method that used digits and dic directly, but they were locals of letterCombinations, invisible to the other method (NameError), with a few syntax errors in between.
The 2022-11 rewrite stored the mapping as self.d2l and passed digits down as a parameter, and passed.

Solution
#

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        letters = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
                   "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
        res = []
        def dfs(i, path):
            if i == len(digits):
                res.append(path)
                return
            for c in letters[digits[i]]:
                dfs(i + 1, path + c)
        dfs(0, "")
        return res

Complexity
#

Time O(4^n · n), space O(n).

Mistakes to Avoid
#

Another method cannot see this method’s local variables (digits, dic); pass them or use a nested function.
An empty string returns [].

Interview Explanation
#

I backtrack one digit per level, appending each of its letters and recording once all digits are processed; an empty input returns an empty list. Time O(4^n · n).