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.

My Answer 1: Accepted (Runtime: 28 ms - 82.26% / Memory Usage: 14.3 MB - 27.50%)

from itertools import product
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        def switch(ch):
            return {
                '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']
            }.get(ch, -1)
        
        if digits == "":
            return []
        
        if len(digits) == 1:
            return switch(digits)
        
        letter = []
        for ch in digits:
            letter.append(switch(ch))
        
        combinations = list(product(*letter))
        
        result = []
        for i in combinations:
            convertstr = ""
            for j in range(0, len(digits)):
                convertstr += i[j]
            if convertstr != "":
                result.append(convertstr)
        
        return result

파이썬은 switch 문이 없기 때문에 함수로 만들어줬다
각 숫자에 해당하는 문자의 리스트를 반환하도록 함

from itertools import product 를 이용하면 리스트의 조합을 구해줘서 편했다..^^
리스트 조합들을 가진 combinations 를 str 조합으로 바꿔서 result 에 넣어주고 리턴하면 끝!!

파이썬에서 리스트에 있는 값들의 모든 조합 구하기 참고: https://ourcstory.tistory.com/414

product 함수 말고 직접 구현하려면 backtracking 써야할거 같은데..... my trauma.....
46. Permutations 과 78. Subsets 을 참고해서 해보려했지만... 제겐 에바쎄바입니다..

Approach 1: Backtracking

Solution 1: Runtime: 32 ms - 56.43% / Memory Usage: 14.2 MB - 77.05%

class Solution:
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        phone = {'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']}
                
        def backtrack(combination, next_digits):
            # if there is no more digits to check
            if len(next_digits) == 0:
                # the combination is done
                output.append(combination)
            # if there are still digits to check
            else:
                # iterate over all letters which map 
                # the next available digit
                for letter in phone[next_digits[0]]:
                    # append the current letter to the combination
                    # and proceed to the next digits
                    backtrack(combination + letter, next_digits[1:])
                    
        output = []
        if digits:
            backtrack("", digits)
        return output

냅 다 외 워