[LeetCode 풀이/python] 17. Letter Combinations of a Phone Number (medium)

문제 설명: 2에서 9 사이의 숫자로 이루어진 문자열 digit 이 주어졌을 때, 해당 숫자가 나타내는 문자들로 만들 수 있는 모든 문자열 조합을 구하시오. 문자열의 순서는 무관하며, 숫자 - 문자 맵핑은 아래와 같음. 1은 어떤 문자도 가리키지 않는다는 점에 주의할 것.) 

 

(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.)

 

예시 1)

입력: digits = "23"  --> 출력: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

 

예시 2)

입력: digits = ""  --> 출력: []

 

예시 3)

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

 

 

제한 조건:

• 0 <= digits.length <= 4
• digits[i] 는 ['2', '9'] 범위 안에 있는 숫자임

 

------ * ------ * ------ * ------

 

[풀이 1안]

• 접근법
  • 각 자리의 숫자가 표현 가능한 문자 갯수가 a, b, c 이면 a * b * c 개의 가능한 모든 조합을 구하는 것 (cf. Cartesian product)
  • 가장 단순하게 풀면 자릿수만큼 for loop 를 반복하면 되겠지만 - 파이썬 내장 라이브러리 itertools 의 product 함수를 쓰면 이걸 한번에 할 수 있다...!
  • product 함수 자체는 인수를 두 개 이상 받을 수 있지만, digits 길이에 따라 모든 케이스를 나눌 순 없으니(...) 세자리 이상인 경우 이전 결과에 한자리씩 cumulatively 더해 구하도록 함

 

• 코드 구현

from itertools import product

def letterCombinations(digits: str) -> List[str]:
    pairs = {'2':'abc', '3':'def', '4': 'ghi', '5':'jkl', '6':'mno', \
             '7':'pqrs', '8':'tuv', '9':'wxyz'}
        
    if len(digits) == 0: return []
    elif len(digits) == 1: return list(pairs[digits])
        
    else:
        res = ['']
        for d in digits:
            cand = pairs[d]
            res = [''.join(i) for i in product(res, cand)]
        return res

 

• 결과
  • 무난히 통과! (섭밋할 때마다 런타임 fluctuations 가 크긴 하지만..)

 

[풀이 2안]

• 접근법
  • 그래도 다른 풀이가 있으려나 하고 discussion 을 확인해봤더니 세자리 이상인 경우 for loop 대신 recursively 표현한 코드를 발견
  • 생각해보면 1안과 기본적인 구조는 같기 때문에 Time Complexity 도 비슷하겠군..

 

• 코드 구현

def letterCombinations(digits):
    pairs = {'2':'abc', '3':'def', '4': 'ghi', '5':'jkl', '6':'mno', \
             '7':'pqrs', '8':'tuv', '9':'wxyz'}
        
    if len(digits) == 0: return []
    elif len(digits) == 1: return list(pairs[digits])
        
    else:
        body = letterCombinations(digits[:-1])
        tail = pairs[digits[-1]]
        return [ b+t for b in body for t in tail ]

 

• 결과
  • 역시나 무난히 통과. 속도도 메모리 사용도 유사한 수준!