문제
https://leetcode.com/problems/letter-combinations-of-a-phone-number/
Letter Combinations of a Phone Number - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
2에서 9까지의 숫자를 포함한 문자열이 주어진다.
각 숫자에는 문자가 매핑된다.
전화번호로 조합 가능한 모든 문자를 출력하자.
풀이 1 - 중복 조합 product
두 개 이상의 리스트의 모든 조합을 구할 때 사용하는 파이썬 내장 함수 'product'를 사용하였다.
시간 : 31ms
from itertools import product
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
dic = {
"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']
}
digits_list = list(digits)
ans = []
if len(digits) == 0:
return []
elif len(digits) == 1:
return dic[digits]
elif len(digits) == 2:
for p in product(dic[digits[0]], dic[digits[1]]):
ans.append("".join(list(p)))
return ans
elif len(digits) == 3:
for p in product(dic[digits[0]], dic[digits[1]], dic[digits[2]]):
ans.append("".join(list(p)))
return ans
elif len(digits) == 4:
for p in product(dic[digits[0]], dic[digits[1]], dic[digits[2]], dic[digits[3]]):
ans.append("".join(list(p)))
return ans
풀이 2 - 백트래킹
백트래킹을 이용해서 모든 경우를 확인하였다.
코드가 확실히 중복 조합보다 간결하다.
시간 : 35ms
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
ans = []
dic = {'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']}
tmp = []
if digits == "": return ans
def dfs(idx):
if idx == len(digits):
ans.append(''.join(tmp))
return
lst = dic[digits[idx]]
for l in lst:
tmp.append(l)
dfs(idx+1)
tmp.pop()
dfs(0)
return ans
총평
시험 칠 때는 백트래킹을 사용하면 좀 더 빨리 문제를 풀 수 있을 것 같다.
'알고리즘 > 파이썬 알고리즘 인터뷰' 카테고리의 다른 글
[LeetCode] 77. Combinations (그래프) (0) | 2022.06.16 |
---|---|
[LeetCode] 46. Permutations (그래프) (0) | 2022.06.16 |
[LeetCode] 200. Number of Islands (그래프) (0) | 2022.06.15 |
슬라이딩 윈도우 (0) | 2022.06.07 |
[LeetCode] 49. Group Anagrams (문자열 조작) (0) | 2022.06.02 |