Letter Combinations of a Phone Number

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

Summary
정렬을 활용하는 문제

---

Description

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.

---

Checking List

• 혼자서 문제를 해결
• 힌트를 보고 해결
• 답을 보고 해결

---

My Answer

• Runtime: 28 ms, faster than 81.19%
• Memory Usage: 14.2 MB, less than 85.76%

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        from itertools import product
        phone = {'1':[],
                 '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']
                }
        
        push = []
        for n in digits:
            push.append(phone[n])
        result = []
        for c in list(product(*push)):
            if c == ():
                continue
            result.append(''.join(c))
        return result

---

Answer Sheet

• 같은 방식이지만 조금 더 간결한 코드

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
	from itertools import product
        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']
        }
	return [''.join(x) for x in product(*(phone[i] for i in digits)) if x]

출처: leetcode:Discuss

• 가장 좋아요가 많았던 코드 (재귀 사용)

class Solution(object):
    def letterCombinations(self, digits):
        mapping = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', 
                   '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
        if len(digits) == 0:
            return []
        if len(digits) == 1:
            return list(mapping[digits[0]])
        prev = self.letterCombinations(digits[:-1])
        additional = mapping[digits[-1]]
        return [s + c for s in prev for c in additional]

출처: leetcode:Discuss

• DFS를 사용한 방법

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

출처: leetcode:Discuss

---

Trial & Error

• 리스트 간 조합을 어떻게 만들지에 대해 고민했는데 itertool의 product를 사용해서 해결했다.

---

Takeaway

• 여러 조합들이 필요한 문제의 경우 DFS를 활용하는 것이 좋을 것 같다.
• itertool.product() 동작 방법에 대해 배우는 계기가 되었다.

def product(*args, repeat=1):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = [tuple(pool) for pool in args] * repeat
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

출처

---