[리트코드] 17. 전화번호 문자 조합 (Python)

Letter Combinations of a Phone Number - LeetCode

문제

2-9 번호에 해당하는 알파벳이 있다. 2-9를 포함한 문자열이 주어질 때, 각 숫자가 나타낼 수 있는 문자들의 조합을 구하여라

과정

1. 백트래킹을 이용하여 문제를 풀어준다.
2. 각 숫자와 문자열을 매핑하는 dictionary를 만들어준다.
3. input으로 들어오는 문자열을 하나 하나 나누어서 받아준다.
4. 입력받은 각 숫자를 키 값으로 문자의 조합을 만들어준다.

 

입력

"23"

출력

["ad","ae","af","bd","be","bf","cd","ce","cf"]

 

풀이

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        dic = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl',
            '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}

        result = []

        def dfs(i, s):
            if i == len(digits):
                result.append(s)
                return
            for c in dic[digits[i]]:
                dfs(i+1, s+c)

        if digits:
            dfs(0, "")
        return result

 

한 줄씩 코드 해석해보기

dic = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl',
        '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}

• 각 숫자와 문자열을 매핑하는 dictionary를 만들어준다.

result = []

• 결과를 출력할 리스트를 생성한다.

def dfs(i, s):
    if i == len(digits):
        result.append(s)
        return

• 백트래킹 함수 dfs를 만들어준다. (길이를 읽어줄 값과 글자를 받는다.)
• i 값이 입력받은 문자열의 길이와 똑같아 지면 result에 글자를 추가해준다.

    for c in dic[digits[i]]:
        dfs(i+1, s+c)

• 입력받은 문자열의 i 번째를 키값으로 한 딕셔너리의 문자를 가져온다.
• for문을 통해 i의 값을 늘리면서 글자에 글자를 붙여준다.

if digits:
    dfs(0, "")
return result

• digits에 값이 있다면 숫자에는 0 문자에는 빈값을 넣어준다. (초기 설정)
• 즉, 백트래킹의 시작점을 잡아준다.