[LEET CODE] 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. 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.   Constraints: 0 <= digits.length <= 4 digits[i] is a digit in the range ['2', '9'].

 

# My Answer

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        l  = {
            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 sum(s1,s2): # 두개 번호의 문자 조합
            answer=[]
            for c in s1:
                for cc in s2:
                    answer.append(c+cc)
            return answer
            
        s=[]
        for d in digits:
            s.append(l[int(d)])
        
        if len(digits)==0:
            return digits
        elif len(digits)==1:
            return l[int(digits)]
            
        a=s[0]
        for i in s[1:]:
            a = sum(a,i)    # 두개리스트씩 조합하기
        return a

 

각번호의 문자들을 각각의 리스트로 저장하고

숫자가 하나만 들어올 경우 그 번호에 해당하는 문자들이 저장된 리스트 리턴

숫자가 여러개일 경우 앞에서부터 두개씩 리스트를 합쳐 문자를 조합한다

앞의 결과를 다시 리스트로 받아서 뒤의 리스트와 조합한다.

 

# Solution 1 - 모든 조합 탐색

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        def dfs(index, path):
            # 끝까지 탐색하면 백트래킹
            if len(path) == len(digits):
                result.append(path)
                return

            # 입력값 자릿수 단위 반복
            for i in range(index, len(digits)):
                # 숫자에 해당하는 모든 문자열 반복
                for j in dic[digits[i]]:
                    dfs(i + 1, path + j)

        # 예외 처리
        if not digits:
            return []

        dic = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
               "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
        result = []
        dfs(0, "")

        return result

digits = "23"일 때

dfs(0,"")

    dfs(1,"a")

         dfs(2,"ad")  -> result = ["ad"]

        dfs(2,"ae")  -> result = ["ad","ae"]

        dfs(2,"af")  -> result = ["ad","ae","af"]

    dfs(1,"b")

         dfs(2,"bd") -> result = ["ad","ae","af","bd"]

        dfs(2,"be") -> result = ["ad","ae","af","bd","be"]

        dfs(2,"bf") -> result = ["ad","ae","af","bd","be","bf"]

    dfs(1,"c")

         dfs(2,"cd") -> result = ["ad","ae","af","bd","be","bf","cd"]

        dfs(2,"ce") -> result = ["ad","ae","af","bd","be","bf","cd","ce"

        dfs(2,"cf") -> result = ["ad","ae","af","bd","be","bf","cd","ce","cf"]

    dfs(2,"d") ->X

    dfs(2,"e") ->X

    dfs(2,"f") ->X