항해99 2주차 - 전화번호문자조합

Today I learned
2022/01/20

회고록

1/20

항해 99, 알고리즘 1주차

교재 : 파이썬 알고리즘 인터뷰

12장 그래프

1. 이론

https://velog.io/@jsw4215/%ED%95%AD%ED%95%B499-2%EC%A3%BC%EC%B0%A8-%EA%B7%B8%EB%9E%98%ED%94%84DFSBFS-%EC%9D%B4%EB%A1%A0-%EC%A0%95%EB%A6%AC

2. 문제

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.

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:

Input: digits = ""
Output: []
Example 3:

Input: digits = "2"
Output: ["a","b","c"]

Constraints:

0 <= digits.length <= 4
digits[i] is a digit in the range ['2', '9'].

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

3. MySol

• Recursive DFS

def solution(inputNum):

    dic = {
        "2":"abc",
        "3":"def",
        "4":"ghi",
        "5":"jkl",
        "6":"mno",
        "7":"pqr",
        "8":"stv",
        "9":"wxyz"
    }

    result = []

    def recursive_num(index, alpha):

        if len(alpha) == len(inputNum):
            result.append(alpha)
            return

        for i in range(index, len(inputNum)):
            for j in dic[inputNum[i]]:
                recursive_num(i+1, alpha + j)

    recursive_num(0,"")

    return result

if __name__ == '__main__':

    inputNum = '23'

    result = solution(inputNum)

    print('result : ' + str(result))

4. 배운 점

• 해당 문제는 재귀함수로 모든 경우의 수를 조합하는 방법으로, 이해하기 어려웠다.
• 하지만, 이해하게 되면 재귀함수를 적용하는데 도움이 된다.

5. 총평

재귀, DFS 훈련