[Leetcode] 17. Letter Combinations of a Phone Number_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '17. Letter Combinations of a Phone Number'에 대해서 살펴보고자 합니다. 

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Letter Combinations of a Phone Number' 알고리즘 문제

 

STEP 2. 'Letter Combinations of a Phone Number' 코드(code)

 

STEP 3. 'Letter Combinations of a Phone Number' 해설

 

STEP 4. 'Letter Combinations of a Phone Number' solution

 

반응형

 

STEP 1. 'Letter Combinations of a Phone Number' 알고리즘 문제

 

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 digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

---

2-9 사이의 숫자를 포함하는 문자열이 주어지면 숫자가 나타낼 수 있는 가능한 모든 문자 조합을 반환합니다. 모든 순서를 반환하면 됩니다. 전화 버튼과 마찬가지로 숫자와 글자의 매핑이 아래에 제시되어 있습니다. 1은 어떤 문자에도 매핑되지 않습니다.

---

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

 

---

STEP 2. 'Letter Combinations of a Phone Number' 코드(code)

 

■ Runtime: 39 ms, faster than 59.57% of Python3 online submissions for Letter Combinations of a Phone Number.

■ Memory Usage: 13.9 MB, less than 80.42% of Python3 online submissions for Letter Combinations of a Phone Number.

 

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        phone_map = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl',
                     '6':'mno', '7':'pqrs', '8': 'tuv', '9':'wxyz'}
        
        if digits == "":
            return []
        
        numbers = list(phone_map[digits[0]])
        
        for digit in digits[1:] :
            numbers = [old + new for old in numbers for new in list(phone_map[digit])]
            
            
        return numbers

---

STEP 3. 'Letter Combinations of a Phone Number' 해설

 

처음에는 행렬 간 곱을 활용해서 문제를 풀려고 했습니다. (np.dot) 예를 들어, digits 23는 "a, b, c" (3, 1) 행렬과 "d, e, f" (3, 1) 행렬의 곱으로 (3, 3) 행렬로 구하려고 했습니다 (2.Transpose * 3) 다만, slice와 string의 행렬 간 곱이 제대로 구현하기 어려워서 결국에는 포기하였습니다. 

 

이후에는 이전 list (old)와 현재 list (new)의 이중 반복문을 통해 문제를 풀었습니다.

 

 

STEP 4. 'Letter Combinations of a Phone Number' solution

 

추가적으로, Leetcode에 공유된 discussion 코드를 살펴보겠습니다.

 

■ Runtime: 82 ms, faster than 5.25% of Python3 online submissions for Letter Combinations of a Phone Number.

■ Memory Usage: 14 MB, less than 32.53% of Python3 online submissions for Letter Combinations of a Phone Number.

 

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        dictionary = {'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']}
        self.dic = dictionary
        self.solution = []
        self.sol(list(digits), "", len(digits))
        return self.solution
    
    def sol(self, digits, s, size):
            if len(s) == size: # append only in the right moment when string size is equal to the number of digits.
                self.solution.append(s)
                
            if not digits: return 0 # dont go further in the recursion.    
            
            for digit in digits:
                temp = digits[:] # copying the list.
                temp.remove(digit) # removing the digit, letters are unique.  
                for letter in self.dic[digit]:
                    self.sol(temp, s + letter, size)
                return 0 # return to break, before taking all combinations.

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '17. Letter Combinations of a Phone Number'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.