17. Letter Combinations of a Phone Number

Problem

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

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

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

Thought Process

The problem can be structured as a tree, as shown in below

White Board

Below is the white board:

Code

class Solution:

    def _findcombo(self, digits, idx, s):
        # s stores the string of digits[0, idx-1]
        # find the letter corresponding to digits[idx], then got the solution of digits[0,idx]
        letter_map = {
            2: "abc",
            3: "cdf",
            4: "ghi",
            5: "jkl",
            6: "mno",
            7: "pqrs",
            8: "tuv",
            9: "wxyz"
        }

    def letterCombinations(self, digits: str) -> List[str]:
        pass

Complexity

  • Time complexity is O(n)

Optimization

Maybe have an iterative solution...