[LeetCode] 17. Letter Combinations of a Phone Number

Medium

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 digits 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: []

 

 

나의 코드

class Solution(object):
    res = []  # list of results
    letter = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]

    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        self.res = [] # 결과 배열 초기화
        if digits == "": return []
        self.dfs(digits, 0, []) # DFS

        return self.res

    def dfs(self, d1, cnt, d2):
        """
        :param d1: str 탐색하려는 번호
        :param cnt: int 길이
        :param d2: List[char] 찾은 letters
        """
        if len(d1) == cnt:
            self.res.append("".join(d2)) # add to list res
        else:
        	idx = int(d1[cnt]) # 탐색할 number에서 letter를 찾을 index
            for j in range(len(self.letter[idx])): # letter
                d2.append(self.letter[idx][j]) # add a letter to d2
                self.dfs(d1, cnt + 1, d2) # DFS
                del d2[len(d2) - 1] # 추가했던 letter를 삭제

• DFS