[LeetCode] 17. Letter Combinations of a Phone Number (그래프)

문제

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

Letter Combinations of a Phone Number - LeetCode

2에서 9까지의 숫자를 포함한 문자열이 주어진다.

각 숫자에는 문자가 매핑된다.

전화번호로 조합 가능한 모든 문자를 출력하자.

 

풀이 1 - 중복 조합 product

 

두 개 이상의 리스트의 모든 조합을 구할 때 사용하는 파이썬 내장 함수 'product'를 사용하였다.

시간 : 31ms

 

from itertools import product
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        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']
              }
        digits_list = list(digits)
        ans = []
        if len(digits) == 0:
            return []
        elif len(digits) == 1:
            return dic[digits]
        elif len(digits) == 2:
            for p in product(dic[digits[0]], dic[digits[1]]):
                ans.append("".join(list(p)))
            return ans
        elif len(digits) == 3:
            for p in product(dic[digits[0]], dic[digits[1]], dic[digits[2]]):
                ans.append("".join(list(p)))
            return ans
        elif len(digits) == 4:
            for p in product(dic[digits[0]], dic[digits[1]], dic[digits[2]], dic[digits[3]]):
                ans.append("".join(list(p)))
            return ans

 

풀이 2 - 백트래킹

 

백트래킹을 이용해서 모든 경우를 확인하였다.

코드가 확실히 중복 조합보다 간결하다.

시간 : 35ms

 

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        ans = []
        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']}
        tmp = []
        
        if digits == "": return ans
                
        def dfs(idx):
            if idx == len(digits):
                ans.append(''.join(tmp))
                return
            lst = dic[digits[idx]]
            for l in lst:
                tmp.append(l)
                dfs(idx+1)
                tmp.pop()
        dfs(0)
        return ans

 

총평

시험 칠 때는 백트래킹을 사용하면 좀 더 빨리 문제를 풀 수 있을 것 같다.