[LeetCode]Letter Combinations of a Phone Number

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

Letter Combinations of a Phone Number - LeetCode

 

문제 분석

번호가 주어졌을 때 핸드폰 자판을 통해 입력가능한 조합을 모두 구하는 문제입니다.

 

처음 시도한 답안

import itertools


class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits == '':
            return []

        char_mapping = {
            '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'],
        }
        chars = []

        for digit in digits:
            chars.append(char_mapping[digit])

        answer = list(''.join(x) for x in itertools.product(*chars))
        
        return answer

접근 방법

1. 주어진 숫자가 없다면 빈 배열을 return 합니다.
2. 각 번호당 입력이 가능한 문자를 매핑하는 딕셔너리를 만듭니다.
3. digits를 순회하면서 chars에 리스트들을 추가합니다.
4. 두개 이상의 리스트끼리 데카르트 곱을 구해주는 itertools.prodct를 이용합니다.
5. 문자열을 연결시키기 위해 결과를 join 합니다.

파이썬이 제공해주는 함수를 이용한 풀이입니다. 간단하게 풀 수는 있었지만 코드로써 데카르트곱을 구하는 방법도 도전해보았습니다.

 

두번째로 시도한 답안 

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits == '':
            return []

        char_mapping = {"2":"abc", '3':"def", '4':"ghi", '5':"jkl", '6':"mno", '7':"pqrs", '8':"tuv", '9':"wxyz"}
        chars = []

        for digit in digits:
            chars.append(char_mapping[digit])

        answer = ['']
        for char in chars:
            answer = [x + y for x in answer for y in char]
        
        return answer

접근 방법

1. 맵핑 딕셔너리에서 리스트를 문자열로 바꾼것을 제외하고 첫번째 방법과 전부 동일합니다.
2. 데카르트 곱을 구현하기 위해 다중 루프를 이용한 리스트 컴프리헨션을 사용합니다.

다음과 같은 순서대로 answer가 채워집니다.

answer : ['a', 'b', 'c']
answer : ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

 

세번째로 시도한 답안

class Solution(object):
    def letterCombinations(self, digits):
        if not digits:
            return []
        
        mapping = {"2":"abc", '3':"def", '4':"ghi", '5':"jkl", '6':"mno", '7':"pqrs", '8':"tuv", '9':"wxyz"}
        answer = []
        
        self.dfs(mapping, digits, "", answer)
        
        return answer
    
    def dfs(self, mapping, digits, path, answer):
        if not digits:
            answer.append(path)
            return 

        for char in mapping[digits[0]]:
            self.dfs(mapping, digits[1:], path+char, answer)

접근 방법

1. dfs를 통해 구하는 방식입니다.
2. digits가 없다면 answer 리스트에 path를 추가하고 종료합니다.
3. 가장 앞에 위치한 digit을 골라 가능한 char들을 반복합니다.
4. digits는 하나씩 앞에서 제거해나가고, path값에 char를 더합니다.

dfs(mapping, "23", "", answer)
    dfs(mapping, "3", "a", answer)
    	dfs(mapping, "", "ad", answer)
    	dfs(mapping, "", "ae", answer)
    	dfs(mapping, "", "af", answer)
    dfs(mapping, "3", "b", answer)
    	dfs(mapping, "", "bd", answer)
    	dfs(mapping, "", "be", answer)
    	dfs(mapping, "", "bf", answer)
    dfs(mapping, "3", "c", answer)
    	dfs(mapping, "", "cd", answer)
    	dfs(mapping, "", "ce", answer)
    	dfs(mapping, "", "cf", answer)

재귀하는 호출을 파악하면 위와 같습니다. 가장 안쪽에 있는 depth들이 answer에 하나씩 추가됩니다.

처음부터 문제를 접근할 때 재귀적인 방식을 떠올리는 것은 참 어려운 것 같습니다.