17. Letter Combinations of a Phone Number
Medium
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 1:
Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = "" Output: []
Example 3:
Input: digits = "2" Output: ["a","b","c"]
Constraints:
0 <= digits.length <= 4digits[i]is a digit in the range['2', '9'].
풀이
1. 데카트르트 곱을 이용한 풀이
from itertools import product
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
# 예외처리
if digits == "":
return digits
# 각 번호의 문자열
dig = {
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']
}
# 문자열 하나가 들어왔을 경우 조합할 경우는 없다
if len(digits) == 1:
return dig[int(digits)]
# 데카르트 곱을 이용한 집합 구성
com = product(*[dig[int(i)] for i in digits])
# 튜플 -> 문자열
result = [''.join(c) for c in com]
return result-
처음에 문제를 풀때 dfs로 풀생각하지 않고, 조합을 이용해서 풀면 좋겠다라는 생각을 했다. 그래서 각 번호가 만들 수 있는 문자를 하나씩 꺼내어 만들 수 있는 모든 문자열을 구하였다.
-
위의 각 집합의 요소를 하나씩 구성하는 것을 데카르트 곱 이라고 하고 python의
itertools.product()메소드를 이용하여 쉽게 구할 수 있다.
2. dfs/백트래킹 을 이용한 풀이
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
def dfs(index, path):
# 각 버튼의 문자열을 하나씩 검사하면 종료
if len(path) == len(digits):
result.append(path)
return
# 입력값 자릿수 단위 반복(다음 레벨의 노드)
for i in range(index, len(digits)):
# 숫자에 해당하는 모든 문자열 반복(인접 리스트)
for j in dic[digits[i]]:
dfs(i + 1, path + j)
# 예외 처리
if not digits:
return []
# 버튼 별 문자열
dic = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
result = []
dfs(0, "")
return result- dfs의 백트래킹을 이용하여 각 숫자의 문자열을 백트래킹을 이용하여 list에 추가하는 방식이다. 그래프 탐색의 dfs와는 조금 다른 듯 보이나 문자열을 깊이우선 탐색하여 백트래킹을 이용하여 조합한 문자열을
append하는 원리는 비슷하다.
Reference
- 책 : 파이썬 알고리즘 인터뷰
게으른 개발자