[leetcode] letter combinations of a phone number

letter combinations of a phone number

• "2~9" 의 8가지 숫자의 조합으로 된 문자열을 입력으로
• 각 숫자는, 문자열 집합의 문자들 중 하나의 문자로 대응될수 있음
• 숫자열이 주어졌을때 조합가능한 모든 문자열 리턴

Solution 1

• itertools의 product 이용
• 곱집합

code 1

from itertools import product
class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        book = {
            '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']
        }
        if not digits : return []
        prev = map(''.join,product(book[digits[0]]))
        for digit in digits[1:]:
            next = book[digit]
            prev = map(''.join,product(prev,next))
        return list(prev)

solution2

• dfs를 이용해 재귀적으로 해결
• 종료조건 : 깊이가 len(digits) 와 같아질때, 경로를 결과에 추가하고 종료

code 2

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        book = {
            '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']
        }

        paths = []

        if not digits: return paths

        def dfs(index, path):
            if index == len(digits):
                paths.append(path)
                return

            for letter in book[digits[index]]:
                dfs(index + 1, path + letter)

        for letter in book[digits[0]]:
            dfs(1, letter)

        return paths

시간복잡도

n : len(digits)
4 : 하나의 숫자와 대응되는 집합의 최대크기
O(4^n)