LeetCode - 17. Letter Combinations of a Phone Number

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

description

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.

example

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Input: digits = ""
Output: []

Input: digits = "2"
Output: ["a","b","c"]

Constraints

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

풀이

코드

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        phone = { '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']}
        result = []
        
        for d in digits:
            if len(result) > 0 :
                newResult = []
                while len(result) > 0 :
                    string = result.pop()
                    for ch in phone[d] :
                        newResult.append(string+ch)
                result = newResult
            else :
                for ch in phone[d] :
                    result.append(ch)
        
        return result

결과

Runtime: 32 ms, faster than 56.14% of Python3 online submissions for Letter Combinations of a Phone Number.
Memory Usage: 14.2 MB, less than 76.16% of Python3 online submissions for Letter Combinations of a Phone Number.

설명

일단 각 숫자별로 딕셔너리를 이용해서 배열을 선언했다. 그리고 리턴할 result도 빈 배열로 초기화를 한다. 파라미터로 주어진 문자열을 하나씩 순회하는데, 처음에는 꺼내올 애들이 없으므로 길이가 0일 때는 그냥 딕셔너리 value를 하나씩 넣어주도록 한다.

이후부터는 newResult라는 배열을 하나 선언해준 후, result에서 pop을 하고 해당 문자열 + value의 각 문자를 더한 것들을 newResult에 추가해둔다. 다 순회하면 result에 다시 레퍼런스를 할당하도록 한다.