17-letter-combinations-of-a-phone-number¶
Try it on leetcode
Description¶
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'].
Solution(Python)¶
class Solution:
def __init__(self):
self.hashTable = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz",
}
self.hashList = [
"0",
"1",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz",
]
def letterCombinations(self, digits: str) -> List[str]:
return self.dfs(digits)
# Time Complexity: O(4^n)
# Space Complexity: O(4^n)
def bfs(self, digits: str) -> List[str]:
n = len(digits)
if n == 0:
return []
res = []
queue = deque([""])
while queue:
s = queue.popleft()
if len(s) == n:
res.append(s)
else:
for letter in self.hashList[int(digits[len(s)])]:
queue.append(s + letter)
return res
# Time Complexity: O(4^n*n)
# Space Complexity: O(n)
def dfs(self, digits: str) -> List[str]:
n = len(digits)
if n == 0:
return []
res = []
def backtrack(candidate, i):
if len(candidate) == n:
res.append(candidate)
return
for j in range(i, n):
for code in self.hashTable[digits[j]]:
candidate += code
backtrack(candidate, j + 1)
candidate = candidate[:-1]
backtrack("", 0)
return res