[Python] LeetCode - Letter Combinations of a Phone Number

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

Letter Combinations of a Phone Number - LeetCode

# 외국 문제풀이 사이트인 LeetCode문제이다. 영어문제를 해석하면서 풀어야해서 영어실력 증진에도

  도움이 되는 것 같다.

 

# '백트래킹' 기초를 연습하기 위해 푼 문제이다.

 

# class와 letterCombinations 함수까지는 기본으로 주어지고 letterCombinations 함수만 내가 작성하면 된다.

   (프로그래머스와 비슷한 듯)

 

# 먼저 숫자 키패드에 해당하는 문자들을 저장하는 dic을 만든다.

   답을 출력할 dab배열을 만들고 BT함수에 0과 ''을 넣고 함수를 실행시킨다.

 

# BT함수: num은 digits[index]이고 그 num에 해당하는 문자들을 c에 할당한다.

                  c에 있는 원소들을 하나하나 돌면서 BT(index +1, letter + i)를 재귀적으로 실행한다.

  (종료조건):   index가 digits의 길이보다 같거나 커지면 digits숫자에 해당하는 조합을 다 찾은 것이므로

               dab배열에 letter를 append해주고 함수호출을 종료한다.

             

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        def BT(index, letter):
            if index >= len(digits):
                dab.append(letter)
                return
            num = digits[index]
            c = dic[num]
            for i in c:
                BT(index + 1, letter + i)
                
        dic = {'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"]}
        dab = []
        BT(0, '')
        return [] if digits == "" else dab

# 처음에 BT(0, '')을 실행하면(digits: "23"인 경우) num에 digits[0]인 "2"가 들어오고

   c에는 ["a","b",c"]가 들어온다. 그리고 반복문을 돌며 BT(1, "a")가 실행되고 BT(2, "ad")가 실행되고 ...

   끝까지 간 뒤(index가 2인경우) dab에 "ad"를 넣고 돌아와서 BT(2, "ae")가 실행되는 식으로

   백트래킹이 되는 것을 확인 할 수 있다.