리트코드 17번 Letter Combinations of a Phone Number (python)

Problem

LeetCode - The World's Leading Online Programming Learning Platform

Solution

from typing import List

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

        answer = []
        def dfs(idx, word):
            if idx >= len(digits):
                answer.append(word)
                return

            char_list = letter_dict[digits[idx]]

            for c in char_list:
                dfs(idx+1, word+c)

        if len(digits):
            dfs(0, "")
        return answer

dfs를 이용하여 마지막 layer에서 만든 단어를 추가하였다.

이 문제에서는 다이얼에 중복되는 글자가 없어서 중복되는 단어가 없다. 만약 중복이 생길 수 있다면 answer에 list가 아닌 set을 사용하여 중복을 제거할 수 있다.

Reference

파이썬 알고리즘 인터뷰 33번