input :
- digits
output :
- digits으로 입력 가능한 모든 문자열들을 출력하시오.
조건 :
- 0 <= len(digits) <= 4
Solution explain : Solution1
idea
- queue를 이용하여 digits의 첫 숫자부터 마지막 까지를 모두 만들자.
- next_idx를 이용하여 digits의 숫자를 접근하고 그 값이 len(digits)와 동일하면 모두 만든 것이라고 판단할 수 있다.
- 재귀를 만든다는 생각으로 점화식을 만들어서도 이를 수행할 수 있다.
주의
- ""을 입력할 수도 있으니 0부터 시작을 하거나 len(digits) == 0이면 []을 리턴하게 해도 된다.
from typing import List
from collections import deque
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
ret = []
data = { 2:"abc", 3:"def",
4:"ghi", 5:"jkl", 6:"mno",
7:"pqrs", 8:"tuv", 9:"wxyz"}
target_len = len(digits)
if target_len == 0:
return ret
q = deque([("", 0)])
while q:
cha, next_idx = q.popleft()
digit = int(digits[next_idx])
next_idx += 1
for next_cha in data[digit]:
temp_cha = cha
temp_cha += next_cha
if next_idx == target_len:
ret.append(temp_cha)
continue
q.append((temp_cha, next_idx))
return ret
s = Solution()
print(s.letterCombinations("23"))
print(s.letterCombinations(""))
print(s.letterCombinations("2"))