17. Letter Combinations of a Phone Number

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 digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

 

 

Example 1:

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

Example 2:

Input: digits = "" Output: []

Example 3:

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

 

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        
        if digits == "":
            return []
        
        dic = {
        '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']
        }

        n = len(digits)
        if n == 1:
            return dic[digits]
        
        
        l = []
        for i in range(n):
            tmp = l
            if i==0:
                l = dic[digits[i]]
            else:
                l = []

                for j in tmp:
                    for k in dic[digits[i]]:
                        l.append(j + k)

        return l

- tmp 활용하여 업데이트 하는 방식

- dfs 형식으로 풀어도 되는 문제