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 digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
(geeksforgeeks) 이미지 첨부
[입력 조건]
0 <= digits.length <= 4
digits[i] is a digit in the range ['2', '9'].
[내 풀이]
from collections import deque
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
# refer dict
numDict = {"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"]}
resultList = []
if not digits:
return resultList
queue = deque()
queue.append("")
while queue:
combination = queue.popleft()
print(combination)
# If the combination length matches the length of digits, it's a complete combination
if len(combination) == len(digits):
resultList.append(combination)
continue
# Iterate through the letters corresponding to the current digit
for letter in numDict[digits[len(combination)]]:
queue.append(combination + letter)
return resultList
먼저, 주어진 숫자에 따라 연관된 알파벳들을 담은 딕셔너리를 생성하여 문자열 처리를 수행하는 방법이 떠올랐습니다. 이 문제에서는 딕셔너리를 활용하여 각 숫자에 해당하는 알파벳들을 조합하여 가능한 모든 문자열 조합을 생성했습니다.
또한, 해결에는 너비 우선 탐색(BFS) 알고리즘을 사용했습니다. BFS는 가까운 노드부터 탐색하며 최단 경로를 찾는데 효과적인 알고리즘입니다. deque를 사용하여 BFS를 구현하면 데이터를 효율적으로 처리할 수 있습니다.
구체적으로는 빈 문자열부터 시작하여 각 숫자에 해당하는 알파벳을 조합하고, 조합된 문자열을 큐에 추가하는 방식으로 모든 가능한 조합을 찾았습니다. 이 과정을 반복하여 큐가 빌 때까지 모든 조합을 탐색하고 결과 리스트에 저장하여 반환하였습니다.
[출처]
https://leetcode.com/problems/letter-combinations-of-a-phone-number/
