ch12-2(leetcode 17). 전화번호 문자 조합

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 17번 ( https://leetcode.com/problems/letter-combinations-of-a-phone-number/ )

 

풀이 1. 

재귀함수를 이용해서 풀 수 있다.

딕셔너리를 이용해서 각 digits의 자리수를 key로, 해당 자리수의 문자열 리스트를 value로 저장한다. 

 

그리고 내부 함수를 선언하여 재귀함수로 사용한다. digits의 맨 뒤의 자리수에서부터 맞는 문자열을 리스트로 리턴하고, 해당 리스트의 앞에다가 붙여 준다. 

 

digits="234"를 예로 들어보자. 

 

"3"과 "4"의 관계를 보면, "4"에서는 뒤의 문자열이 더 이상 없어서 딕셔너리에서 "4"에 해당하는 알파벳 리스트인 ["g","h","i"] 값을 불러온다. 

"3"에서는 "4"에서 리턴된 ["g","h","i"]의 각 요소를 for loop로 순회하면서 각 요소의 앞에다가 "3"에 해당하는 알파벳 리스트인 ["d","e","f"]의 각 요소들을 붙여준다. 

 

전체 코드는 다음과 같다. 

class Solution(object):

    def letterCombinations(self, digits):
        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 comb(length):
            if length == len(digits)-1:
                return phone[digits[length]]

            result = []
            for i in phone[digits[length]]:
                for j in comb(length+1):
                    result.append(i+j)
            return result

        if digits == "":
            return []
        return comb(0)