[Leetcode] 17. Letter Combinations of a Phone Number

🔗 Problem Link

Letter Combinations of a Phone Number - LeetCode

---

❔Thinking

• 2에서 9까지 숫자가 주어질 때, 각 숫자에 적힌 알파벳으로 가능한 조합을 모두 담은 리스트를 반환한다.

---

💻Solution

1. 조합을 활용한 풀이

from itertools import product
def letterCombinations(self, digits: str) -> List[str]:
    if len(digits) == 0: # digit이 없을 때 예외처리
        return []

    phone_table = {
        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']
    }

    # n에 digit에 적힌 알파벳 리스트로 담기
    n = []
    for dig in digits:
        n.append(phone_table[int(dig)])


    return [''.join(combi) for combi in list(product(*n))]

 

2. DFS를 활용한 풀이

def letterCombinations(self, digits: str) -> List[str]:
    if not digits:
        return []

    phone_table = {
        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']
    }

    result = []
    stack = [(0, [])]

    while stack:
        index, chars = stack.pop()
        if index == len(digits):
            result.append("".join(chars))
        else:
            for char in phone_table[int(digits[index])]:
                stack.append([index+1, chars + [char]])
    return result

---

🗝️keypoint

1. DFS 풀이를 위해서는, stack에 현재 문자열의 길이와 다음 숫자로 가능한 문자열을 모두 포함시켜야 한다.