log 2022-03-12

leetcode study - letter-combinations-of-a-phone-number

---

• sport
  • leet - letter-combinations-of-a-phone-number

sport

leet - letter-combinations-of-a-phone-number

• 현재 구성된 조합 리스트에 대해, 입력된 다음 키를 돌면서 리스트에 추가해서, 다음 조합 리스트를 만들고, 이를 반복 (그대로 구현)

• 현재 구성된 조합이 없는 경우 확산이 되질 않아서 첫 item ‘

  ‘로 시작, 결과 계산할 때 모든 item[0] 제외

• 엣지케이스 예외처리 안해서 1번 틀림. (입력 없는 경우)
• 시간복잡도 O(3.5^n)

py solution

# for leetcode
digit_to_keys = {
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz',
}


def get_keys_of_digit(key):
    return digit_to_keys[key]


def get_keys_of_digits(keys):
    digits_list = []
    for key in keys:
        digits = get_keys_of_digit(key)
        digits_list.append(digits)
    return digits_list

# 어떤 형태로든 각 숫자는 기존의 입력을 3~4배 하게 된다.
# 각 숫자를 순회하면서, 기존의 입력 규칙에 따라 뻥튀기 하는 것

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits) == 0:
            return []
        cur = ['|']
        tmp = None
        for digit in digits:
            tmp = []
            for item in cur:
                for key in get_keys_of_digit(digit):
                    tmp.append(item + key)
            cur = tmp
        return [item[1:] for item in cur]

---