[LeetCode] 17. Letter Combinations of a Phone Number

접근

• 난이도가 있는 문제는 아니지만 특수한 상황에 탐색 기법을 사용하여 솔루션을 작성할 수 있느냐를 묻는 문제
• 예제가 부실함. 3가지 이상의 예제도 좀 넣어주지...

 

솔루션

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        answer = []
        digits_length = len(digits)

        if digits_length == 0:
            return answer

        # create mapped list
        # this result dial list to be
        # ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        dial = ["", ""]
        index = 97
        for i in range(2, 10):
            dial_string = chr(index) + chr(index+1) + chr(index+2)
            index += 3
            # 7 and 9 has 4 charactors
            if i == 7 or i == 9:
                dial_string = dial_string + chr(index)
                index += 1
            dial.append(dial_string)

        def dfs(answer_string, index):
            if len(answer_string) == digits_length:
                answer.append(answer_string)
                return
            
            # search next index
            for i in dial[int(digits[index])]:
                dfs(answer_string + i, index + 1)
        
        dfs("", 0)
        return answer