문제 이해

입력

• 문자열 배열 digits
• 1≤ digits.len ≤ 4

출력

• 숫자에 할당된 모든 문자열의 순열 배열

요구 사항

• 각 문자에는 할당된 문자가 있음
• 순열의 길이는 digits.len와 같음

문제 풀이

• 백트래킹을 사용한 문제
  • 시간 복잡도는 *O*(3^*N ** 4^*M*)
  • 함수에 index, path를 파라미터로 추가
  • 결과를 저장할 문자열 배열 res
  • 재귀 함수에 진입하면,
    1. index가 digits.len와 같은지 체크
       • 같다면 res에 path추가
       • 아니라면, digits_dict[digits[index]]에서 다음에 연결할 문자열 꺼내서 for문 돌리기

Code

class Solution(object):
    def letterCombinations(self, digits):

        if not digits:
            return []

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

        res = []

        def back_traking(index, path):
            if index == len(digits):
                res.append(''.join(path))
                return

            words = digits_dict[digits[index]]

            for word in words:
                path.append(word)
                back_traking(index+1, path)
                path.pop()
        
        back_traking(0, [])

        return res