[ LeetCode - 17 ] Letter Combinations of a Phone Number

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

Letter Combinations of a Phone Number - LeetCode

전형적인 백트래킹 문제가 아닌가 싶다.

별다른 조건 없이 만들 수 있는 모든 조합을 만들어서 리스트에 담아 리턴하면 되는 문제

---

[ 📌 풀이 ]

• digits의 길이가 사실 만들어지는 조합들의 문자열 길이와 같기 때문에 종료 조건으로 잡았는데 (comIdx를 사용해도 무방)
• 빈칸으로 들어오는 경우가 있는데 이때 빈 리스트를 return 해줘야 한다.

---

[ 📌 코드 - Python ]

"""
# Author    : Lee In Bok 
# Date      : 2023.10.31(Tue)
# Spend Time: 13m 34s
# Runtime   : 37 ms (Beats 67.73%)
# Memory    : 16.2 MB (Beats 62.40%)
# Algoritm  : Backtracking
"""

from typing import List

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits == "":
            return []

        button = {
            '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']
        }
        ans = []

        def backtracking(combIdx:int, comb: str):
            if len(digits) == len(comb):
                ans.append(comb)
                return

            for letter in button[digits[combIdx]]:
                backtracking(combIdx + 1, comb + letter)

        backtracking(0, "")

        return ans

---

[ 📌 결과 ]

시간은 전부 1ms 차이여서 돌릴 때마다 차이가 생기는거지 코드적으로 최적화는 하지 않았다.

[ Result ]