-
Notifications
You must be signed in to change notification settings - Fork 4.7k
Expand file tree
/
Copy pathletter_combination.py
More file actions
49 lines (40 loc) · 1.22 KB
/
Copy pathletter_combination.py
File metadata and controls
49 lines (40 loc) · 1.22 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
"""
Letter Combinations of a Phone Number
Given a digit string, return all possible letter combinations that the
number could represent using a telephone keypad mapping.
Reference: https://leetcode.com/problems/letter-combinations-of-a-phone-number/
Complexity:
Time: O(4^n) where n is the number of digits
Space: O(4^n) for the result list
"""
from __future__ import annotations
def letter_combinations(digits: str) -> list[str]:
"""Return all letter combinations for a digit string.
Args:
digits: A string of digits (2-9).
Returns:
A list of all possible letter combinations.
Examples:
>>> letter_combinations("23")
['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
"""
if digits == "":
return []
keypad_map = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz",
}
combinations: list[str] = [""]
for digit in digits:
expanded: list[str] = []
for existing in combinations:
for char in keypad_map[digit]:
expanded.append(existing + char)
combinations = expanded
return combinations