17. Letter Combinations of a Phone Number

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/letter-combinations-of-a-phone-number
• topics: String Manipulation

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

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

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        mapping = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz",
        }
        perms = []
        
        if not digits:
            return perms
 
        def permute(prefix, digits):
            if not digits and prefix:
                perms.append(prefix)
                return
            
            for c in mapping[digits[0]]:
                permute(prefix + c, digits[1:])
 
        permute('', digits)
        return perms